An upper triangular matrix A is invertible if and only if all of its diagonal elements are nonzero.

Ashley J.S Mills

October 24, 2005

0.1 The Claim
0.2 The if part
0.3 the only if part
0.4 Conclusion

0.1 The Claim

Claim: An upper triangular matrix A is invertible if and only if all of its diagonal elements are nonzero.

Proof: The proof follows in three parts.

0.2 The if part

Claim: If all the diagonal elements of an upper triangular matrix A are nonzero then the matrix A is invertible.

Proof:

If A is invertible, then there exists a matrix X such that

XA = I = Y

where X = A^-1.

Element y_ij of the result matrix Y = XA is deﬁned as

∑n yij = xikakj k=1

where n is the dimensionality of the n × n matrix A.

Since Y = I,

{ 0 if i ⁄= j yij = 1 if i = j

Thus there exist three cases to satisfy: i = j, i < j, and i > j, which shall be considered in turn.

In the ﬁrst case, i = j

n yii = ∑ xikaki=!1 k=1

For k > i, a_ki = 0 because A is upper triangular and therefore

∑ i yii = xikaki=!1 k=1

By setting x_ik to 0 when k < i it follows that

yii = xiiaii=!1

which is satisﬁed by setting x_ii to -1
aii . Therefore by setting x_ik to 0 when k < i and by setting x_ii to 1-
aii the correct value for y_ij when i = j is obtained.

Now consider the second case, namely i < j

∑n ! yij = xikakj= 0 k=1

from the argument for the i = j case, x_ik = 0 when k < i, and when k > j, a_kj = 0 because A is upper triangular, so

j y = ∑ x a =!0 ij k=i ik kj

this can be rewritten as

j∑-1 yij = xikakj +xijajj != 0 k=i

and therefore by setting

--∑jk-=1i xikakj xij = ajj

it follows that

j∑-1 j-∑ 1 yij = xikakj - xikakj = 0 k=i k=i

and so for i < j, y_ij !
= 0 has been satisiﬁed.

The third case occurs when i > j

n yij = ∑ xikakj=!0 k=1

Now, from the i = j case, when k < i, x_ik = 0, but since in this third case i > j, or in other words j < i, it follows that when

k ≤ j < i

x_ik = 0, and so for k ≤ j, x_ik = 0. But for k > j, a_kj = 0 because A is upper triangular and therefore

∑n yij = xikakj = 0 k=1

because for k ≤ j, x_ik = 0 and for k > j, a_kj = 0. Which means thta when i > j, y_ij !
= 0 is satisﬁed.

Thus it has been shown how to set the elements of X to satisfy the identity XA = I, and therefore if all of the diagonal elements of an upper triangular matrix A are nonzero, it follows that A is invertible, being what it was required to prove.

0.3 the only if part

Claim: If an upper triangular matrix A is invertible, then all of its diagonal elements are nonzero.

Proof:

First observe that to say A is invertible is to say that there exists a matrix X such that

XA = Y = I

The proof that if A is invertible then all its diagonal elements are nonzero, is inductive and proceeds from the following claim.

If a_pp is nonzero and for all j ≤ p it is true that x_ij = 0 when i > j then a_(p+1)(p+1) is nonzero and for all j ≤ (p + 1) it is true that x_ij = 0 when i > j.

For the base case a₁₁ it is necessary to show that a₁₁ is nonzero and that for all j ≤ 1, x_ij = 0 when i > j. Subsequent proof of the inductive step will establish proof of the original claim, namely that all the diagonal elements of A are nonzero.

Consider the element y₁₁ of the result matrix XA

∑n y11 = x1kak1 != 1 k=1

Since A is upper triangular, when k > 1, a_k1 = 0 therefore

y11 = a11x11 != 1

Both a₁₁ and x₁₁ must be nonzero for the result to be equal to 1, therefore a₁₁ is nonzero.

Now to show that for j ≤ 1, x_ij = 0 when i > j. Consider the case for j < 1, and assume that the claim is false, this means that there exists an i > j, where j < 1 such that x_ij 0, however there exists no such x_ij since there is no j < 1 and therefore the assumption is false and it is true that for j < 1, x_ij = 0 when i > j.

Consider the case when j = 1, it must be shown that when i > j, x_ij = 0. This is demonstrated by considering the elements y_i1 for i > 1, in this case y_ij 0 because i j.

∑ ! yi1 xikak1= 0 k=1

However, as before, when k > 1, a_k1 = 0 because A is upper triangular and therefore

! yi1 = xi1a11 = 0

but a₁₁ was already shown to be nonzero and hence x_i1 !
= 0. Therefore for i > j, x_i1 = 0.

Thus, the base case, namely that a₁₁ 0 and that for j ≤ 1, x_ij = 0 when i > j, has been proven.

It is now necessary to demonstrate that the inductive step holds. It is required to show that if a_pp 0 and for j ≤ p, x_ij = 0 when i > j, that a_(p+1)(p+1) 0 and for j ≤ (p + 1), x_ij = 0 when i > j.

Assuming then that the precondition holds, namely that a_pp is nonzero and that for j ≤ p, x_ij = 0 when i > j, consider the element y_(p+1)(p+1) which must be equal to 1

n y(p+1)(p+1) = ∑ x(p+1)kak(p+1) != 1 k=1

it was claimed that for j ≤ p, x_ij = 0 when i > j, therefore in the sum above, for k ≤ p, x_(p+1)k = 0 since (p + 1) is greater than k in each case, therefore

∑n ! y(p+1)(p+1) = x(p+1)kak(p+1)= 1 k=(p+1)

however when k > (p + 1), a_k(p+1) = 0 since A is upper triangular, and therefore

y(p+1)(p+1) = x(p+1)(p+1)a(p+1)(p+1)=!1

both terms must thus be nonzero and thus it has been shown that a_(p+1)(p+1) is nonzero.

Now it is necessary to show that for j ≤ (p + 1), it is true that x_ij = 0 when i > j. For j ≤ p it was already established that x_ij = 0 when i > j by the induction step precondition, therefore it has already been shown that for j < (p + 1), x_ij = 0 when i > j and need only be shown for j = (p + 1). Consider the elements y_i(p+1) when i > (p + 1), it is necessary to show that these elements each equal 0

n y = ∑ xika =!0 i(p+1) k=1 k(p+1)

since in each case i > (p + 1), for k ≤ p, x_ik = 0 and therefore

∑n ! yi(p+1) = xikak(p+1)= 0 k=(p+1)

however when k > (p + 1), a_k(p+1) = 0 because A is upper triangular and therefore

yi(p+1) = xi(p+1)a(p+1)(p+1)=!0

yet a_(p+1)(p+1) 0 and therefore x_i(p+1) !
= 0 for i > (p + 1) and hence it has been shown that when i > j, x_i(p+1) = 0. Therefore for j ≤ (p + 1), x_ij = 0 when i > j and the induction step has been proven.

Therefore when an upper triangular matrix A is invertible, all of its diagonal elements are nonzero, being what it was required to prove.

Note, that this induction also proves that if an upper triangular matrix A is invertible, then the inverse X will also be upper triangular since the induction shows that for j ≤ n, x_ij = 0 when i > j (n is the size of the n×n matrix A).

0.4 Conclusion

It was shown ﬁrst that if all of the diagonal elements of an upper triangular matrix A are nonzero, then that matrix A is invertible.

It was shown second that if an upper triangular matrix A is invertible, then all of its diagonal elements are nonzero.

Thus what was set out to prove has been established, namely that, an upper triangular matrix A is invertible if and only if all of its diagonal elements are nonzero.

Q.E.D