Prove that for any square matrix, an invertible matrix B exists, so that BA is triangular

Question

I'm given a matrix A, its dimensions are n x n.

I am required to prove that an invertible matrix B exists, such that the product of the matrices BA is triangular.

Any help?

Answer 1

Gaussian elimination (also known as row reduction) transforms a square matrix into an upper triangular matrix. Every elementary row operation

• multiplying a row by a number different from $0$
• summing a row with another row multiplied by any number
• swapping two rows

can be realized as the multiplication by an invertible matrix. Namely, the matrix realizing each operation is the one obtained from the identity matrix subject to the same elementary row operation.

Therefore the successive elementary row operation give $$ U = E_k E_{k-1} \dots E_2 E_1 A $$ where $U$ is in (reduced) row echelon form (hence triangular). Then $$ A=(E_k E_{k-1} \dots E_2 E_1)^{-1}U $$ is the required decomposition.

Answer 2

If $A=QR$ is a QR factorisation of $A$, then $Q^*A=R$. So the statement is true with $B=Q^*$.