Linear Algebra

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

linear combination problems and solutions in linear algebra

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?

Add to solve later

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}.\]

Add to solve later

More from my site

$Find the Vector Form Solution to the Matrix Equation $A\mathbf{x}=\mathbf{0}$$ Find the Vector Form Solution to the Matrix Equation $A\mathbf{x}=\mathbf{0}$ Find the vector form solution $\mathbf{x}$ of the equation $A\mathbf{x}=\mathbf{0}$, where $A=\begin{bmatrix} 1 & 1 & 1 & 1 &2 \\ 1 & 2 & 4 & 0 & 5 \\ 3 & 2 & 0 & 5 & 2 \\ \end{bmatrix}$. Also, find two linearly independent vectors $\mathbf{x}$ satisfying […]
$The Column Vectors of Every $3\times 5$ Matrix Are Linearly Dependent$ The Column Vectors of Every $3\times 5$ Matrix Are Linearly Dependent (a) Prove that the column vectors of every $3\times 5$ matrix $A$ are linearly dependent. (b) Prove that the row vectors of every $5\times 3$ matrix $B$ are linearly dependent. Proof. (a) Prove that the column vectors of every $3\times 5$ matrix $A$ are linearly […]
Basis and Dimension of the Subspace of All Polynomials of Degree 4 or Less Satisfying Some Conditions. Let $P_4$ be the vector space consisting of all polynomials of degree $4$ or less with real number coefficients. Let $W$ be the subspace of $P_2$ by \[W=\{ p(x)\in P_4 \mid p(1)+p(-1)=0 \text{ and } p(2)+p(-2)=0 \}.\] Find a basis of the subspace $W$ and determine the dimension of […]
Linear Independent Continuous Functions Let $C[3, 10]$ be the vector space consisting of all continuous functions defined on the interval $[3, 10]$. Consider the set \[S=\{ \sqrt{x}, x^2 \}\] in $C[3,10]$. Show that the set $S$ is linearly independent in $C[3,10]$. Proof. Note that the zero vector […]
How to Find a Basis for the Nullspace, Row Space, and Range of a Matrix Let $A=\begin{bmatrix} 2 & 4 & 6 & 8 \\ 1 &3 & 0 & 5 \\ 1 & 1 & 6 & 3 \end{bmatrix}$. (a) Find a basis for the nullspace of $A$. (b) Find a basis for the row space of $A$. (c) Find a basis for the range of $A$ that consists of column vectors of $A$. (d) […]
Column Rank = Row Rank. (The Rank of a Matrix is the Same as the Rank of its Transpose) Let $A$ be an $m\times n$ matrix. Prove that the rank of $A$ is the same as the rank of the transpose matrix $A^{\trans}$. Hint. Recall that the rank of a matrix $A$ is the dimension of the range of $A$. The range of $A$ is spanned by the column vectors of the matrix […]
The Set of Vectors Perpendicular to a Given Vector is a Subspace Fix the row vector $\mathbf{b} = \begin{bmatrix} -1 & 3 & -1 \end{bmatrix}$, and let $\R^3$ be the vector space of $3 \times 1$ column vectors. Define \[W = \{ \mathbf{v} \in \R^3 \mid \mathbf{b} \mathbf{v} = 0 \}.\] Prove that $W$ is a vector subspace of $\R^3$. […]
A Condition that a Vector is a Linear Combination of Columns Vectors of a Matrix Suppose that an $n \times m$ matrix $M$ is composed of the column vectors $\mathbf{b}_1 , \cdots , \mathbf{b}_m$. Prove that a vector $\mathbf{v} \in \R^n$ can be written as a linear combination of the column vectors if and only if there is a vector $\mathbf{x}$ which solves the […]