Prove/Disprove

T

TheWrathOfMath

Junior Member
Joined
Mar 31, 2022
Messages
162
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.
 
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.
 
blamocur said:
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.
Click to expand...
Right. Will I not be able to prove it using only row echelon reduction, though?
 
TheWrathOfMath said:
Do you perhaps know how should I approach this problem?
Click to expand...

Let [imath]A[/imath] be an [imath]n \times n[/imath] matrix.

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

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

[math]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)[/math]
Can you do this?

If this is too much try doing it first with a smaller ([imath]2\times 2[/imath] or [imath]3\times 3[/imath]) matrix.
 
TheWrathOfMath said:
Right. Will I not be able to prove it using only row echelon reduction, though?
Click to expand...

I've done this again :( -- I've mistakenly assumed that [imath]A[/imath] is a given and you need to figure out [imath]B[/imath] to make [imath]AB[/imath] upper triangular. Very sorry!
 
blamocur said:
Let [imath]A[/imath] be an [imath]n \times n[/imath] matrix.

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

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

[math]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)[/math]
Can you do this?

If this is too much try doing it first with a smaller ([imath]2\times 2[/imath] or [imath]3\times 3[/imath]) matrix.
Click to expand...

You can do row echelon reduction in a similar way by computing left multipliers in a similar manner.
 
Here is my modified post on how to start row echelon reduction applying left-multipliers.

Let [imath]B[/imath] be a [imath]n \times n[/imath] matrix.

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

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

[math]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)[/math]
 
blamocur said:
I've done this again :( -- I've mistakenly assumed that [imath]A[/imath] is a given and you need to figure out [imath]B[/imath] to make [imath]AB[/imath] upper triangular. Very sorry!
Click to expand...
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.
 
TheWrathOfMath said:
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.
Click to expand...

Did you mean [imath]E_1 E_2...E_k B[/imath] is upper rectangular? (In which case [imath]A = E_1E_2...E_k[/imath]
 
blamocur said:
Did you mean [imath]E_1 E_2...E_k B[/imath] is upper rectangular? (In which case [imath]A = E_1E_2...E_k[/imath]
Click to expand...
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).
 
TheWrathOfMath said:
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.
Click to expand...
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.
 
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?
 
TheWrathOfMath said:
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).
Click to expand...
Now, to actually prove it you have to prove that matrices [imath]E_1,E_2,...,E_k[/imath] actually exist. That would be my expectation if I were giving this assignment.
 
You must log in or register to reply here.
Top