Number of solutions of system of linear equations based on rank

Created: 02-18-2020

Last updated: 02-18-2020

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:

1. \( 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^{n-m} \) 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 \( n-m \).


2. \( 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(x-y)=0 \). This would lead to suppose that \( x-y=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 \( x-y=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^{n-r} \).