Triangular matrix

Suppose that is lower triangular, so that whenever . By definition, the entries of the transpose satisfyTherefore, whenever . Hence, is upper triangular.

Analogous to the previous one.

Suppose that and are two lower triangular matrices. We need to prove thatwhenever . But, when , we have thatwhere: in step we have used the fact that because ; in step we have used the fact that because .

The proof is analogous to the previous one.

Let us first prove the "only if" part. Suppose a lower triangular matrix has a zero entry on the main diagonal on row , that is,Consider the sub-matrix formed by the first rows of . The -th column of is zero because , and all the columns to its right are zero because is lower triangular. Then, has at most non-zero columns. As a consequence, it has at most linearly independent columns. Thus, its column rank is at most . Since row rank and column rank coincide, this implies that has at most linearly independent rows. As a consequence, the rows of are not linearly independent. But the rows of are also rows of . Therefore, the rows of are not linearly independent, is not full-rank and it is not invertible. To sum up, we have proved that if there is a zero entry on the main diagonal of , then is not invertible. As a consequence, is invertible only if there are no zero entries on the main diagonal. We now need to prove the "if part" (if there are no zero entries on the main diagonal, then is invertible). We are going to prove it by contradiction. If is not invertible, then its rows are not linearly independent and one of them (suppose it is the -th row) can be written as a linear combination of the other rows:If there are other rows below , with indices , then their coefficients in the linear combination must be zero. In particular, must be zero because the -th row is the only one having a non-zero entry in the -th column and has a zero entry in the -th column. Therefore,By the same token, must be zero because the -th row is the only one in the linear combination having a non-zero entry in the -th column and has a zero entry in the -th column. Thus,We repeat this reasoning until we deduce that As a consequence,But this is impossible because has a non-zero entry in the -th column and all have zero entries in that column. Thus, we have proved by contradiction that if all the diagonal entries of are non-zero, then no row of can be written as a linear combination of the others. As a consequence, the rows are linearly independent and is invertible. We have now proved the proposition for lower triangular matrices. The proof for upper triangular matrices is similar (replace columns with rows).

Let be a lower triangular matrix. Denote by the columns of . By definition, the inverse satisfieswhere is the identity matrix. The columns of are the vectors of the standard basis. The -th vector of the standard basis has all entries equal to zero except the -th, which is equal to . By the results presented in the lecture on matrix products and linear combinations, the columns of satisfyfor . This is a system of equations that can be written asNote that the constants on the right-hand side are zero in all equations but the -th. Since is invertible, its diagonal elements () are non-zero. Since , the first equation has solution . By plugging this solution into the second equation, we get (because ). Then, we solve the third equation, and so on, until we reach the -th equation, where for the first time we find a non-zero solution . Thus, the entries of the column vector above the -th row are all zero. But is the -th column of and the statement holds true for all . As a consequence, all the entries of whose row index is less than the column index are zero. In other words, is lower triangular. The proof for upper triangular matrices is analogous.

Remember that a matrix is said to be in row echelon form if and only if 1) all its non-zero rows have a pivot (i.e., a non-zero entry such that all the entries to its left and below it are equal to zero) and 2) all its zero rows are located below the non-zero rows. Suppose is an invertible upper triangular matrix. Then, has no zero rows because all its diagonal entries are non-zero. Furthermore, each row of contains a diagonal entry, which is a pivot because it is non-zero and it has only zeros below it and to its left. Therefore, is in row echelon form.

This is a straightforward consequence of the previous proposition. We just need to use the facts that: 1) the transpose of an upper triangular matrix is lower triangular; 2) the transpose of a matrix in row echelon form is in column echelon form.

Let be a square matrix in row echelon form. Scan the rows of from top to bottom in search of pivots. You will find a pivot on each row until you get to the zero rows. Each pivot you find is below and to the right of the previous one. Therefore, the pivots are always to the right of the main diagonal. Entries to the left of the pivots must be zero. Therefore, a fortiori, entries to the left of the main diagonal are zero. Hence, is upper triangular.

This is an immediate consequence of the previous proposition. We just need to use the facts that the transpose of a matrix in row echelon form is in column echelon form and the transpose of an upper triangular matrix is lower triangular.