Number of solutions of system of linear equations based on rank
Created: 02182020
Last updated: 02182020
Suppose you're asked to determine the number of solutions of the system \( Ax=b \) with \( A \in \mathbb{R}^{m \times n} \), \( x \in \mathbb{R}^{n \times 1} \) and \( b \in \mathbb{R}^{m \times 1} \)
\[ \begin{pmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \cdots & a_{m,n} \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{pmatrix} \]
First let's write the matrix as a vector of its columns
\[ A = \begin{pmatrix} a_1 & a_2 & \dots & a_n \end{pmatrix} \]
where
\[ a_1 = \begin{pmatrix} a_{1,1} \\ a_{2,1} \\ \vdots \\ a_{m,1} \end{pmatrix}, a_2 = \begin{pmatrix} a_{1,2} \\ a_{2,2} \\ \vdots \\ a_{m,2} \end{pmatrix}, \cdots , a_n = \begin{pmatrix} a_{1,n} \\ a_{2,n} \\ \vdots \\ a_{m,n} \end{pmatrix} \]
Suppose \( rank(A)=m \). This means that a basis for the image of the matrix \( A \) is made of \( m \) linearly independent vectors. Remember that \( m \) is also the number of rows of the matrix. Though we don't know if \( m \) is larger, smaller or equal to \( n \) (number of columns). So we need to study three different cases:

\( m < n \)
For simplicity suppose that the vectors of the basis are the first \( m \) vectors. That said, it's convenient to write the matrix as
\[ A = \begin{pmatrix} a_1 & a_2 & \dots & a_m & a_{m+1} & \dots & a_n \end{pmatrix} \]
If \( b \in Im(A) \) it means that \( b \) can be obtained as a linear combination of the basis vectors
\[ x_1a_1+x_2a_2+\dots +x_ma_m=b \]
therefore we must not consider the remaining columns of the matrix, so we put
\[ x_{m+1}=\dots=x_n=0 \]
This means we have found one solution of the system \( Ax=b \) and that is
\[ x=\begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_m \\ 0 \\ \vdots \\ 0 \end{pmatrix} \]
Now the question is: is this the only solution? The answer is NO.
Next question is: if it's not the only one, how many are there? Let's find out.
We found the first solution using the equation
\[ x_1a_1+x_2a_2+\dots +x_ma_m + x_{m+1} a_{m+1} + \dots + x_n a_n=b \]
where \( x_1, x_2, \dots , x_m \in \mathbb{R} \) and \( x_{m+1}=\dots=x_n=0 \).
It's clear that \( b \) is determined by the first \( m \) unknowns and the remaining unknowns must be zero.
We know that the columns \( a_{m+1},\dots,a_n \) are linearly dependent. This means that we can obtain a null linear combination of those columns with the unknowns not all to zero. In other words, it means that there exist at least one set of unknowns \( x_{m+1},\dots,x_n \) not all zero such that \( x_{m+1}a_{m+1}+\dots +x_na_n=0 \)
Once you find one set of those unknowns, you can write a new solutions
\[ \overline x=\begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_m \\ x_{m+1} \\ \vdots \\ x_n \end{pmatrix} \]
You can double check that \( \overline x \) is a solution: it needs to be \( A \overline x = b \)
\[ A\overline x= x_1a_1+x_2a_2+\dots +x_ma_m+x_{m+1}a_{m+1}+\dots +x_na_n \]
But we know that \( x_{m+1}a_{m+1}+\dots +x_na_n=0 \) so that becomes
\[ A\overline x= x_1a_1+x_2a_2+\dots +x_ma_m = b \]
The number of solutions depends on the number of combinations of the unknowns \( x_{m+1},\dots,x_n \) not all zero such that \( x_{m+1}a_{m+1}+\dots +x_na_n=0 \). Though if one combination exists, there exist infinite. See this example
\[ 4x_1+5x_2+9x_3+7x_4=0 \]
One solution is
\[ x_1 = 1, x_2 = 1, x_3 = 1, x_4 = 0 \]
But if you choose any \( \alpha \in \mathbb{R} \), the following is a solution as well
\[ x_1 = \alpha, x_2 = \alpha, x_3 = \alpha, x_4 = 0 \]
This means you have infinite solutions.
It is common to say that a system \( Ax=b \) has \( \infty^{nm} \) solutions because, although they are infinite, the number of solutions depends on the number of linearly dependent columns of the matrix \( A \) which is equal to the total number of columns minus the rank (number of rows), thus \( nm \).

\( m=n \)
Then \( A \) is a square matrix there are as many equations as there are unknowns and the solution must be unique.
If there were two different solutions, \( x \) and \( y \), it'd be true that \( Ax=b \) and \( Ay = b \). Subtructing the two, we'd have \( A(xy)=0 \). This would lead to suppose that \( xy=0 \) because we know that all the columns of \( A \) are linearly independent so the only way to obtain a null linear combination is to multiply for zero. But supposing that \( xy=0 \implies x=y \) breaks the hypothesis that \( x \) and \( y \) are two different solutions.
Now suppose that \( rank(A)=r < m \). Similarly to before, It can be proved that the number of solutions in this case is \( \infty^{nr} \).