[Math] Rank of homogeneous linear system of equations

homogeneous equationlinear algebramatrix-ranksystems of equations

Question – Summarized

Given a linear system of homogeneous equations, we know that there exists a trivial solutions where all the variables are zero. Thus, we can only have a system with one solution (the trivial one), or infinitely many solutions.

Can the ranks of the system's coefficient matrix and augmented matrix immediately tell us which?

My thoughts

I have the understanding that yes, it can.

Let $A$ be the system's coefficient matrix, and $A'$ be the system's augmented matrix, and assume we have a linear system of homogeneous equations, with the augmented matrix:

$$ A' =
\begin{bmatrix}
a_{11} & a_{12} & a_{13} & 0 \\
a_{21} & a_{22} & a_{23} & 0 \\
a_{31} & a_{32} & a_{33} & 0 \\
\end{bmatrix}
$$

and coefficient matrix:

$$ A=
\begin{bmatrix}
a_{11} & a_{12} & a_{13} \\
a_{21} & a_{22} & a_{23} \\
a_{31} & a_{32} & a_{33} \\
\end{bmatrix}
$$

If we reduce both these to row-echelon form, assume we end up with the following results, and let $*$ be any non-zero real number.

$$\text{ref}(A) = \begin{bmatrix}
* & * & * \\
0 & * & * \\
0 & 0 & * \\
\end{bmatrix}$$

$$\text{ref}(A') = \begin{bmatrix}
* & * & * & 0 \\
0 & * & * & 0 \\
0 & 0 & * & 0 \\
\end{bmatrix}$$

Let $n$ be the number of variables (so $n=3$ for this example).

We can see that $\text{rank}(A) = \text{rank}(A') = n$, which leads us to the conclusion that we have one distinct solution, which would be the trivial $(0, 0, 0)$.

However, if the third row ended up being the zero vector, we would have $\text{rank}(A) = \text{rank}(A') < n$, and we'd end up with a free variable, and thus infinitely many solutions.

My conclusion, which I'm hoping for verification to

We must conclude that if $\text{rank}(A) = \text{rank}(A') = n$, the system has a single solution. And if $\text{rank}(A) = \text{rank}(A') < n$, the system has infinitely many solutions in addition to the trivial one.

Addendum: The case where $\text{rank}(A) < \text{rank}(A') $ cannot occur for inhomogeneous systems, since it would require a pivot element in the right-most columns of $A'$. If that was the case, the system wouldn't be homogeneous. Since the assumption leads to a contradiction, the ranks must always be the same.

Would love to get some feedback on my thought process.

Best Answer

Yes, you can discern the number of solutions for a homogeneous linear system of equations immediately from either the rank of the coefficient matrix or the rank of the augmented matrix. Let's consider the general case that $A = \begin{bmatrix} a_1 & a_2 & \cdots a_n \end{bmatrix}\in\mathbb{R}^{m\times n}$, where $a_i\in\mathbb{R}^m$ is the $i$th column of $A$.

First, as you correctly pointed out, the rank of the coefficient matrix equals that of the augmented matrix. To see why, note that the rank of a matrix is usually defined as the dimension of its range. Defining $A' = \begin{bmatrix} A & 0_{m\times 1} \end{bmatrix}$, we have that

\begin{align*} \text{rank}(A) ={}& \dim\{ Ax : x\in\mathbb{R}^n \} \\ ={}& \dim\left\{ \begin{bmatrix} A & 0_{m\times 1} \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} : (x,y)\in\mathbb{R}^n \times\mathbb{R} \right\} \\ ={}& \dim\{A'z : z\in\mathbb{R}^{n+1}\} \\ ={}& \text{rank}(A'). \end{align*}

Therefore, let's focus our attention on just the coefficient matrix $A$. There are two cases:

  • Case 1: $\text{rank}(A)=n$. In this case, the set $\{a_1,a_2,\dots,a_n\}$ is linearly independent, and therefore $x_1a_1 + x_2a_2 + \cdots + x_na_n = 0$ only if $x_1=x_2=\cdots=x_n=0$. Hence, $Ax=0$ implies that $x=0$, so there is one solution (the trivial solution).
  • Case 2: $\text{rank}(A)<n$. In this case, the set $\{a_1,a_2,\dots,a_n\}$ is linearly dependent, and therefore there exists a nonzero linear combination of the columns of $A$ that sum to zero. That is, $Ax = x_1a_1 + x_2a_2 + \cdots + x_na_n = 0$ for some $x\in\mathbb{R}^n\setminus\{0\}$. Now, let $\alpha\in\mathbb{R}$ and define $\tilde{x} = \alpha x$. We have that $A\tilde{x} = \alpha Ax = 0$. Since $\alpha$ was chosen arbitrarily, we see that there is an infinite number of solutions to the homogeneous system of equations.
Related Question