Prove/Disprove

[TheWrathOfMath]

Prove or disprove:
B is a square matrix. There exists an invertible matrix A so that AB is an upper triangular matrix.

I know that this is a true statement, since I managed to find matrices A and B that satisfy the condition.

However, I do not know how to write a proof for the general case.
I know that every matrix in row echelon form is upper triangular.
I also know that there exists a finite number of elementary matrices that when multiplied by A will yield a matrix which is upper triangular: E1...Ek*A (basically the same as performing elementary row operations on A in order to transform it into row echelon form).

Assistance would be highly appreciated.

 

[blamocur]

Similarly to using a matrix on the left for doing row echelon reduction one can work out a symmetrical approach to implement column echelon reduction by multiplying on the right.

 

[TheWrathOfMath]

Similarly to using a matrix on the left for doing row echelon reduction one can work out a symmetrical approach to implement column echelon reduction by multiplying on the right.

Right. Will I not be able to prove it using only row echelon reduction, though?

 

[blamocur]

Right. Will I not be able to prove it using only row echelon reduction, though?

I don't know.

 

[TheWrathOfMath]

I don't know.

Do you perhaps know how should I approach this problem?

 

[TheWrathOfMath]

@Dr.Peterson
Perhaps you could please assist me?

 

[blamocur]

Do you perhaps know how should I approach this problem?

Let $A$ be an $n \times n$ matrix.

First find matrix $P$ such that in matrix $F = AP$ we have non-zero element at location $n,n$, i.e., $f_{n,n} \neq 0$.

Then zero all but one elements of the last row of $F$. I.e., find matrix $Q$ such that matrix $H=FQ$ has all zeros to the left of the diagonal:

$$H= \left( \begin{array}{ccccc} h_{1,1} &h_{1,2} & ... & h_{1,n-1} &h_{1,n} \\ h_{2,1} &h_{2,2} & ... & h_{2,n-1} &h_{2,n} \\ ... & ... & ... & ... & ... \\ h_{n-1,1} &h_{n-1,2} & ... & h_{n-1,n-1} &h_{n-1,n} \\ 0 & 0 & ... & 0 & h_{n,n} \end{array} \right)$$
Can you do this?

If this is too much try doing it first with a smaller ($2\times 2$ or $3\times 3$) matrix.

 

[blamocur]

Right. Will I not be able to prove it using only row echelon reduction, though?

I've done this again -- I've mistakenly assumed that $A$ is a given and you need to figure out $B$ to make $AB$ upper triangular. Very sorry!

 

[blamocur]

Let $A$ be an $n \times n$ matrix.

First find matrix $P$ such that in matrix $F = AP$ we have non-zero element at location $n,n$, i.e., $f_{n,n} \neq 0$.

Then zero all but one elements of the last row of $F$. I.e., find matrix $Q$ such that matrix $H=FQ$ has all zeros to the left of the diagonal:

$$H= \left( \begin{array}{ccccc} h_{1,1} &h_{1,2} & ... & h_{1,n-1} &h_{1,n} \\ h_{2,1} &h_{2,2} & ... & h_{2,n-1} &h_{2,n} \\ ... & ... & ... & ... & ... \\ h_{n-1,1} &h_{n-1,2} & ... & h_{n-1,n-1} &h_{n-1,n} \\ 0 & 0 & ... & 0 & h_{n,n} \end{array} \right)$$
Can you do this?

If this is too much try doing it first with a smaller ($2\times 2$ or $3\times 3$) matrix.

You can do row echelon reduction in a similar way by computing left multipliers in a similar manner.

 

[blamocur]

Here is my modified post on how to start row echelon reduction applying left-multipliers.

Let $B$ be a $n \times n$ matrix.

First find matrix $P$ such that in matrx $F = PA$ we have non-zero element at location $1,1$, i.e., $f_{1,1} \neq 0$.

Then zero all but the first elements of the first column of $F$. I.e., find matrix $Q$ such that matrix $H=QF$ has all zeros in the first column below the diagonal:

$$H = \left( \begin{array}{ccccc} h_{1,1} &h_{1,2} & ... & h_{1,n-1} &h_{1,n} \\ 0 &h_{2,2} & ... & h_{2,n-1} &h_{2,n} \\ ... & ... & ... & ... & ... \\ 0 &h_{n-1,2} & ... & h_{n-1,n-1} &h_{n-1,n} \\ 0 & h_{n,2} & ... & h_{n,n-1} & h_{n,n} \end{array} \right)$$

 

[TheWrathOfMath]

I've done this again -- I've mistakenly assumed that $A$ is a given and you need to figure out $B$ to make $AB$ upper triangular. Very sorry!

From what I understood the solution is related to the fact that every matrix in row echelon form is an upper triangular matrix, and that since it is given that A is an invertible matrix, we can conclude that there exists a finite number of elementary matrices that when multiplied by A will yield a matrix which is upper triangular: E1...Ek*A.
I just did not manage to figure out how to use this piece of information in order to prove that AB is an upper triangular matrix.
And I know that this is a correct statement, since I managed to find matrices A and B that satisfy the condition.

 

[blamocur]

From what I understood the solution is related to the fact that every matrix in row echelon form is an upper triangular matrix, and that since it is given that A is an invertible matrix, we can conclude that there exists a finite number of elementary matrices that when multiplied by A will yield a matrix which is upper triangular: E1...Ek*A.
I just did not manage to figure out how to use this piece of information in order to prove that AB is an upper triangular matrix.
And I know that this is a correct statement, since I managed to find matrices A and B that satisfy the condition.

Did you mean $E_1 E_2...E_k B$ is upper rectangular? (In which case $A = E_1E_2...E_k$

 

[TheWrathOfMath]

Did you mean $E_1 E_2...E_k B$ is upper rectangular? (In which case $A = E_1E_2...E_k$

Yes.
This is what I did in order to prove it, actually.
I figured that there is a finite number (k) of elementary matrices such that when multiplied by B, it will transform B into row echelon form, hence upper triangular. Therefore, I will let A=E1...Ek, and then I will get E1...Ek*B, which will be matrix B in row echelon form (upper triangular).

 

[Steven G]

Prove or disprove:
B is a square matrix. There exists an invertible matrix A so that AB is an upper triangular matrix.

I know that this is a true statement, since I managed to find matrices A and B that satisfy the condition.

You are given a square matrix B. You do not know its size nor entries. However you claimed to find a matrix A such that AB is upper triangular. Do you really think that you found A?

Just because you found a pair of matrices, A and B, where AB is U.T. does not guarantee that given any square matrix B that you can find A where AB is U.T.

 

[Steven G]

6 and 14 are both even integers and their sum is also even. So we can conclude that the sum of two even integers is even?

 

[blamocur]

Yes.
This is what I did in order to prove it, actually.
I figured that there is a finite number (k) of elementary matrices such that when multiplied by B, it will transform B into row echelon form, hence upper triangular. Therefore, I will let A=E1...Ek, and then I will get E1...Ek*B, which will be matrix B in row echelon form (upper triangular).

Now, to actually prove it you have to prove that matrices $E_1,E_2,...,E_k$ actually exist. That would be my expectation if I were giving this assignment.