Conditions for $A\mathbb{x} = \mathbb{b}$ to have solutions
In the article about vector space, we learned that $A\mathbb{x} = \mathbb{b}$ has solutions for some $b$ and is unsolvable for other $b$. Unlike the nullspace, here we only consider the case when $b \neq 0$.
Consider an example, given the matrix $$A = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10 \end{bmatrix}$$
Suppose we are solving the system of equations $A\mathbb{x} = \mathbb{b}$ with $b = (b_1; b_2; b_3)$, then the first thing we are sure about is that $b$ must belong to the column space of $A$. Since we see that row 3 of $A$ is the sum of rows 1 and 2, we have $b_1 + b_2 = b_3$.
The way to prove that $A\mathbb{x} = \mathbb{b}$ has solutions is to use row reduction on the augmented matrix $[A \quad b]$:
$$ \begin{aligned} [A \quad b] \Leftrightarrow \begin{bmatrix} 1 & 2 & 2 & 2 & b_1 \\ 2 & 4 & 6 & 8 & b_2\\ 3 & 6 & 8 & 10 & b_3 \end{bmatrix} & \rightarrow \begin{bmatrix} 1 & 2 & 2 & 2 & b_1 \\ 0 & 0 & 2 & 4 & b_2 - 2b_1\\ 0 & 0 & 2 & 4 & b_3 - 3b_1 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 2 & 2 & 2 & b_1 \\ 0 & 0 & 2 & 4 & b_2 - 2b_1\\ 0 & 0 & 0 & 0 & b_3 - b_2 - b_1 \end{bmatrix}\\ & \rightarrow \begin{bmatrix} 1 & 2 & 0 & -2 & 3b_1 - b_2\\ 0 & 0 & 2 & 4 & b_2 - 2b_1\\ 0 & 0 & 0 & 0 & b_3 - b_2 - b_1 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 2 & 0 & -2 & 3b_1 - b_2\\ 0 & 0 & 1 & 2 & \frac{b_2 - 2b_1}{2}\\ 0 & 0 & 0 & 0 & b_3 - b_2 - b_1 \end{bmatrix} = [R \quad d] \end{aligned} $$
We see that now the matrix after transforming $R$ has the last row as a zero vector.
Therefore, in this system of equations, the condition for $Rx = d$ to have a solution is that the vector $d$ must have the form $(d_1; d_2; 0)$. In other words, for $A\mathbb{x} = \mathbb{b}$ to have a solution in this case, the vector $b$ must have the form $b_3 - b_2 - b_1 = 0$, for example, $b = (1; 5; 6)$.
Note that the solution set $x$ of the system $A\mathbb{x} = \mathbb{b}$ and $Rx = d$ are the same.
Finding the complete solution of Ax = b
After finding the condition for the system of equations to have a solution, we will try to find a particular solution. To do that, we will transform the matrix into echelon form to determine the pivot and free variables. Like the example above, $R$ has 2 pivot variables $x_1$ and $x_3$, meaning we have free variables $x_2$ and $x_4$.
Different from solving the system $A\mathbb{x} = \mathbb{0}$, here we will set all free variables to 0, meaning $x_2 = x_4 = 0$. To understand more, please review my previous posts about echelon form matrices. Now since we have transformed $A\mathbb{x} = \mathbb{b}$ into $Rx = d$, the system looks like:
$$ \begin{aligned} & \begin{bmatrix} 1 & 2 & 0 & -2 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} x_1 \\ 0 \\ x_3 \\ 0 \end{bmatrix} = \begin{bmatrix} -2 \\ 1.5\\ 0 \end{bmatrix}\\ \Leftrightarrow & \begin{cases} x_1 = -2\\ x_3 = \frac{3}{2} \end{cases} \end{aligned} $$
So, we have a particular solution $x_p = (-2; 0; \frac{3}{2}; 0)$.
We only have exactly one particular solution $x_p$ for a system of equations $A\mathbb{x} = \mathbb{b}$. So how do we find other solutions of the system?
We will find $x_n$ such that $Ax_n = 0$.
The reason is that we can add $x_p$ to any $x_n$ on the left-hand side and still obtain $b$ on the right-hand side. This can be easily proven as follows:
$$ \begin{cases} Ax_p = b \\ Ax_n = 0 \end{cases} \Leftrightarrow A(x_p + x_n) = b $$
Therefore, the solution set $x$ of the system of equations $A\mathbb{x} = \mathbb{b}$ is a linear combination of $x_p$ and $x_n$.
$$ x = x_p + cx_n $$
The complete solution of $A\mathbb{x} = \mathbb{b}$ = one particular solution + all nullspace of $A$
Back to the example, we will find the set $x_n$ such that $Rx_n = 0$. If you want to be hardcore, you can calculate $Ax_n = 0$ as well, it’s the same but you will have the opportunity to practice the transformation again.
Since I have already instructed how to solve it in my previous post, I won’t solve it here. I’ll just spoil the answer: the set $x_n$ includes 2 vectors which are $\begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix}$ and $\begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix}$.
So the complete solution of $A\mathbb{x} = \mathbb{b}$ is written as follows:
$$ x_{complete} = \begin{bmatrix} -2 \\ 0 \\ \frac{3}{2} \\ 0 \end{bmatrix} + c_1\begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} + c_2\begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix} $$
The relationship between the rank of a matrix and the solution set $A\mathbb{x} = \mathbb{b}$
Recalling the rank of a matrix is the number of pivot elements in that matrix.
Suppose we have a matrix of size $m \times n$, the rank $r$ of the matrix must obey the constraints $r \leq m, r \leq n$. We will have 2 separate cases when $r = n$ and $r = m$.
The case $r = n$ is when the number of pivot elements = the number of columns in the matrix. We call this full column rank.
Conversely, when $r = m$, meaning the number of pivot elements = the number of rows in the matrix, we call it full row rank.
The possibilities for a linear system $A\mathbb{x} = \mathbb{b}$ when $A$ has rank $r$ are:
- $r = n$ and $r < m$ $\Leftrightarrow Ax = b$ has 0 or 1 solution
- $r = m$ and $r < n$ $\Leftrightarrow Ax = b$ has infinitely many solutions
- $r = m$ and $r = n$ $\Leftrightarrow Ax = b$ has a unique solution
- $r < m$ and $r < n$ $\Leftrightarrow Ax = b$ has 0 or infinitely many solutions
For each possibility, the matrix $R$ also has its own characteristics. We will examine each case specifically. I will update the last case when I truly understand it.
Case $r = n < m$
Considering the case $r = n < m$, please take about 2 - 3’ to note down and think about what will happen when a matrix $A$ has the same number of pivot elements as columns?
Then the matrix $A$ has full column rank, which means $A$ has no free variables, because all columns contain pivots.
Additionally, full column rank indicates that the columns in that matrix are linearly independent. No column can be represented as a linear combination of other columns.
Returning to the problem $A\mathbb{x} = \mathbb{0}$, since there are no free variables, the system of equations only has a unique solution $x = 0$. Moreover, $A\mathbb{x} = \mathbb{b}$ also has a unique solution $x = x_p$.
Example: $A = \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ -2 & -3 \end{bmatrix} \quad ; \quad b = (b_1; b_2; b_3)$
Firstly, to solve the system $A\mathbb{x} = \mathbb{b}$, we find the condition for the system of equations to have a solution.
$$ [A \quad b] = \begin{bmatrix} 1 & 1 & b_1 \\ 1 & 2 & b_2 \\ -2 & -3 &b_3 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 1 & b_1 \\ 0 & 1 & b_2 - b_1 \\ 0 & -1 & b_3 + 2b_1 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 0 & b_1 - b_2 \\ 0 & 1 & b_2 - b_1 \\ 0 & 0 & b_3 + b_2 + b_1 \end{bmatrix} = [R \quad d] $$
Thus, the condition to find a solution for $A\mathbb{x} = \mathbb{b}$ is $b_1 + b_2 + b_3 = 0$. Through the transformation process from $A$ to $R$, we see that $R = \begin{bmatrix} I \end{bmatrix}$, with $I$ being the identity matrix of size $n \times n$.
When encountering $R$ in this form, it is a sign that $Rx = d$ or $A\mathbb{x} = \mathbb{b}$ has 0 or 1 solution.
A matrix $A$ with full column rank has the following properties:
All columns of $A$ are pivot columns (clearly because every column of $A$ contains a pivot)
The matrix has no free variables, so there is no special solution
The nullspace $N(A)$ contains only the zero vector
If $A\mathbb{x} = \mathbb{b}$ satisfies the condition to have a solution, then only one $x$ can be found. Otherwise, $A\mathbb{x} = \mathbb{b}$ is unsolvable
Case $r = m < n$
Contrary to the full column rank matrix, the full row rank matrix indicates that the rows of matrix $A$ are linearly independent.
A matrix with full row rank will not have any row of zeros (because every row contains a pivot).
For a matrix $A$ with $m$ rows and $n$ columns, containing $r = m$ pivots means we have $n - m$ (or $n - r$) free variables. Thus, for any $A\mathbb{x} = \mathbb{b}$ that satisfies the condition to have a solution and $A$ is a matrix with full row rank, we will always find a complete solution for each $b$.
Considering the case $r = m < n$, let’s take the following example:
$$ \begin{aligned} [A \quad b] = \begin{bmatrix} 1 & 1 & 1 & 3 \\ 1 & 2 & -1 & 4 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 1 & 1 & 3 \\ 0 & 1 & -2 & 1 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 0 & 3 & 2 \\ 0 & 1 & -2 & 1 \end{bmatrix} = [R \quad d] \end{aligned} $$
In the full row rank case, we no longer need to find the condition for $A\mathbb{x} = \mathbb{b}$ to have a solution, because we are sure to always find at least one $x$ that satisfies the system.
Returning to the example above, we see that $R$ has the form $\begin{bmatrix} I & F \end{bmatrix}$.
$F$ here tells us the solution of the system $A\mathbb{x} = \mathbb{0}$, meaning we have $x_n = (-3; 2; 1)$ satisfies $Ax_n = 0$. Why is there a 1? Because corresponding to $x_3$ it’s a free variable, so according to the method of solving the system $A\mathbb{x} = \mathbb{0}$, we will assign 1 to find the special solution.
We also infer the particular solution $x_p$ from $d$. In this system of equations, $x_p = (2; 1; 0)$ (because to find the particular solution $x_p$, we will assign all free variables = 0).
A matrix $A$ with full row rank has the following properties:
The matrix $A$ does not have a row of zeros
$A\mathbb{x} = \mathbb{b}$ always finds at least one solution \\ Column space $C(A) \in \mathbf{R}^m$ (because there are $m$ rows and all rows are linearly independent)
Case $r = m = n$
This case occurs with a square matrix $A$.
Taking an example: $A = \begin{bmatrix} 1 & 2 \\ 3 & 1 \end{bmatrix}$
This is probably the easiest case to imagine the matrix $R$: we have a square matrix with $r = m$ and $r = n$, so obviously $R$ is the identity matrix $I$.
$ R = I = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} $
By now, you probably understand why for this case, the system of equations $Rx = d$ or its original form $A\mathbb{x} = \mathbb{b}$ only has a unique solution.
Properties of a square matrix $A$ with full row and full column rank:
The number of pivot elements = the number of rows = the number of columns
All rows of $A$ are linearly independent, and all columns of $A$ are linearly independent
Full row rank implies full column rank, and vice versa
$A$ is invertible
Unique solution to the system of equations $A\mathbb{x} = \mathbb{b}$
Conclusion
Through this post, we have a summary of the conditions for $A\mathbb{x} = \mathbb{b}$ to have solutions, as well as the properties of a matrix $A$ corresponding to these solutions.
In the next posts, we will continue to explore the null space $N(A)$, the linear dependence, the coordinate system, and the least squares solutions. Stay tuned for more exciting discoveries!