# Column Vectors of an Upper Triangular Matrix with Nonzero Diagonal Entries are Linearly Independent

## Problem 654

Suppose $M$ is an $n \times n$ upper-triangular matrix.

If the diagonal entries of $M$ are all non-zero, then prove that the column vectors are linearly independent.

Does the conclusion hold if we do not assume that $M$ has non-zero diagonal entries?

## Proof.

### If the diagonal entries of $M$ are all non-zero, then prove that the column vectors are linearly independent.

Let $\mathbf{x}$ denote an arbitrary column vector of length $n$, and let $\mathbf{0}$ denote the zero vector of the same size.

The columns of $M$ are linearly independent if and only if the only solution to the equation $M \mathbf{x} = \mathbf{0}$ is the vector $\mathbf{x} = \mathbf{0}$.

Consider the upper-triangular matrix
$M = \begin{bmatrix} m_{1, 1} & m_{1, 2} & m_{1, 3} & \cdots & m_{1, n} \\ 0 & m_{2, 2} & m_{2, 3} & \cdots & m_{2, n} \\ 0 & 0 & m_{3, 3} & \cdots & m_{3, n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & m_{n, n} \end{bmatrix}.$

The equation $M \mathbf{x} = \mathbf{0}$ then yields a system of linear equations with $n$ equations and $n$ variables.
To find a solution, consider the augmented matrix $\begin{bmatrix}[c|c] M & \mathbf{0} \end{bmatrix}$.

Because $M$ is upper-triangular, we can use back-substitution to solve. The bottom row of the augmented matrix gives the equation $m_{n, n} x_n = 0$.
By assumption, $m_{n, n} \neq 0$ because it is a diagonal entry. Thus we must have that $x_n=0$.

Next, the second-to-last row in the augmented matrix gives the equation $m_{n-1, n-1} x_{n-1} + m_{n-1, n} x_n = 0$. Because $x_n = 0$ and $m_{n-1, n-1} \neq 0$, we must have that $x_{n-1} = 0$.

We continue working backward in this way to see that $x_i = 0$ for all $1 \leq i \leq n$. Thus $\mathbf{x} = \mathbf{0}$, and so the columns of $M$ must be linearly independent.

### Does the conclusion hold if we do not assume that $M$ has non-zero diagonal entries?

If the diagonal entries of $M$ could be non-zero, then the columns might be linearly dependent. Consider the simple example
$M = \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix}.$

Sponsored Links

### More from my site

#### You may also like...

This site uses Akismet to reduce spam. Learn how your comment data is processed.

##### Write a Vector as a Linear Combination of Three Vectors

Write the vector $\begin{bmatrix} 1 \\ 3 \\ -1 \end{bmatrix}$ as a linear combination of the vectors \[\begin{bmatrix} 1 \\...

Close