The Mysterious Rank (of a Matrix) Demystified

Be the first to leave a comment!
Let us start with the following system of linear equations (written in matrix form):
$$ AX = B\text{ where } A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \cdots & \cdots & \cdots & \cdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix},\, X = \begin{bmatrix} x_{1} \\ x_{2} \\ \cdots \\ x_{n} \end{bmatrix},\, B = \begin{bmatrix} b_{1} \\ b_{2} \\ \cdots \\ b_{m} \end{bmatrix}$$ The augmented matrix of the system is: $$\tilde{A} = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} & b_{1} \\ a_{21} & a_{22} & \cdots & a_{2n} & b_{2} \\ \cdots & \cdots & \cdots & \cdots & \cdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} & b_{m} \end{bmatrix}$$
Let the rank of $ A$ be $ r$. This means that if we reduce the matrix $ A$ to row-reduced echelon form the resulting matrix will have only $ r$ non-zero rows and last $ m - r$ rows be consisting of all zeroes. If we apply the same elementary row operations (which were used to reduce $ A$ to echelon form) on the augmented matrix $ \tilde{A}$, we will get a new matrix, say $ C$, whose first $ n$ columns will be same as the echelon form of $ A$ and one extra column will have some entries $ c_{1}, c_{2}, \ldots, c_{m}$. If the elements $ c_{r + 1}, c_{r + 2}, \ldots, c_{m}$ are all zero then the matrix $ C$ will also be in echelon form with $ r$ non-zero rows and hence will have rank $ r$. If this is not the case (i.e at least one of the numbers $ c_{r + 1}, c_{r + 2}, \ldots, c_{m}$ is not zero) then the augmented matrix will have a rank greater than $ r$ (actually it will be $ r + 1$). In this case we see that the last $ m - r$ equations will be of the form: \begin{align} 0x_{1} + 0x_{2} + \cdots + 0x_{n} &= c_{r + 1}\notag\\ 0x_{1} + 0x_{2} + \cdots + 0x_{n} &= c_{r + 2}\notag\\ \cdots\cdots\cdots &= \cdots\notag\\ 0x_{1} + 0x_{2} + \cdots + 0x_{n} &= c_{m}\notag \end{align} and then we don't have any solution (because the right side of these equations must be zero). Hence we see that that when the rank of augemented matrix, say $ r^{\prime}$ is greater than rank of coefficient matrix then there is no solution to the system of equations.

Let's consider the case when both these ranks are equal. In that case we may have either $ r < n$ or $ r = n$. In case we have $ r = n$, it means that we have $ n$ non-zero rows and each of these non-zero rows have their first non-zero entry in a different column. Since we have only $ n$ columns, it follows that the system of equations will be reduced to \begin{align} x_{1} &+& d_{12}x_{2} &+& d_{13}x_{3} &+& \cdots &+& d_{1n}x_{n} &=& c_{1}\notag\\ 0x_{1} &+& x_{2} &+& d_{23}x_{3} &+& \cdots &+& d_{2n}x_{n} &=& c_{2}\notag\\ \cdots &+& \cdots &+& \cdots &+& \cdots &+& \cdots &=& \cdots\notag\\ 0x_{1} &+& 0x_{2} &+& \cdots &+& 0x_{n - 1} &+& x_{n} &=& c_{n}\notag \end{align} It thus follows that we can find unique value of $ x_{n} = c_{n}$ and substituting backwards we can find unique values of $ x_{n - 1}, x_{n - 2}, \ldots, x_{2}, x_{1}$. Hence in this case we have a unique solution of the system.

In case we have $ r < n$ then we have $ r$ non-zero rows in the echelon form of augmented matrix and let us suppose that the first non-zero entry in these rows occurs in the columns $ k_{1}, k_{2}, \ldots, k_{r}$. We can then evaluate the variables $ x_{k_{1}}, x_{k_{2}}, \ldots, x_{k_{r}}$ in terms of remaining $ n - r$ variables and by giving these $ n - r$ variables arbitrary values we can find an infinity of solutions for the given system.

To reiterate once again:
Solution of System of Linear Equations: Let $ A$ be the coefficient matrix of a system of linear equations in $ n$ variables and let $ \tilde{A}$ be the augmented matrix of the system. Let the rank of $ A$ be $ r$ and the rank of $ \tilde{A}$ be $ r^{\prime}$. Then $ r \leq r^{\prime} \leq n$. The system has
  1. no solution if  $ r < r^{\prime}$
  2. a unique solution if $ r = r^{\prime} = n$
  3. infinitely many solutions if $ r = r^{\prime} < n$
A practical example illustrating these ideas and techniques is as follows: \begin{align} 3x + y - 6z &= -10\notag\\ 2x + y - 5z &= -8\notag\\ 6x - 3y + 3z &= 0\notag \end{align} Clearly the augmented matrix of the system is $$ \begin{bmatrix} 3 & 1 & -6 & -10 \\ 2 & 1 & -5 & -8 \\ 6 & -3 & 3 & 0 \end{bmatrix}$$ We apply elementary row operations to get \begin{align} R_{3} - 2R_{1} &\rightarrow R_{3}\,\, \begin{bmatrix} 3 & 1 & -6 & -10 \\ 2 & 1 & -5 & -8 \\ 0 & -5 & 15 & 20 \end{bmatrix}\notag\\ R_{1} - R_{2} &\rightarrow R_{1}\,\, \begin{bmatrix} 1 & 0 & -1 & -2 \\ 2 & 1 & -5 & -8 \\ 0 & -5 & 15 & 20 \end{bmatrix}\notag\\ R_{3} / (-5) &\rightarrow R_{3}\,\, \begin{bmatrix} 1 & 0 & -1 & -2 \\ 2 & 1 & -5 & -8 \\ 0 & 1 & -3 & -4 \end{bmatrix}\notag\\ R_{2} - 2R_{1} &\rightarrow R_{2}\,\, \begin{bmatrix} 1 & 0 & -1 & -2 \\ 0 & 1 & -3 & -4 \\ 0 & 1 & -3 & -4 \end{bmatrix}\notag\\ R_{3} - R_{2} &\rightarrow R_{3}\,\, \begin{bmatrix} 1 & 0 & -1 & -2 \\ 0 & 1 & -3 & -4 \\ 0 & 0 & 0 & 0 \end{bmatrix}\notag\end{align} From this echelon form we see that $ r = r' = 2$ and $ n = 3$ so that the system has infinitely many solutions. From the echelon form we also see that the system of equations is equivalent to \begin{align} x - z &= -2\notag\\ y - 3z &= -4\notag \end{align} Giving $ z$ an arbitrary value $ c$ we get $ x = c - 2, y = 3c - 4, z = c$ as the solution of the given system.

Homogeneous System of Equations

A slightly simpler case occurs when the system of equations can be represented in the form $ AX = O$ where $ A$ is an $ m \times n$ matrix, $ X$ is the $ n \times 1$ matrix consisting of all variables and $ O$ is the $ m \times 1$ zero matrix whose all entries are zero. This kind of a system is called "homogeneous". In this case there is no need to consider the augmented matrix (because that would just add a column of zeroes to the coefficient matrix and clearly the rank of augmented matrix and that of coefficient matrix would always be same).

It is quite obvious that there is at least one solution in which we put all variables as zero. This is called the trivial solution. In case the rank of coefficient matrix is equal to the number of variables then we have the case of unique solution and therefore only trivial solution exists. In case the rank of coefficient matrix is less than the number of variables we have infinitely many solutions and all of them except one (with all variables as zero) are non-trivial. Hence we have the following theorem:

Solution of Homogeneous System of Equations: If a homogeneous system of linear equations is represented in the matrix form as $ AX = O$ where $ A$ is an $ m \times n$ matrix, $ X$ is $ n \times 1$ matrix consisting of all the variables and $ O$ is the $ m \times 1$ zero matrix consisting of all zero entries then the system has:
  1. trivial solution if $ \text{rank}(A) = n$
  2. non-trivial (infinitely many) solutions if $ \text{rank}(A) < n$
The case of "no solutions" obviously does not arise here.

Thus we complete the theory of system of linear equations which is almost like "in a nutshell" and can be understood by anyone who knows how to add, subtract, multiply or divide numbers. The hard truth is that this simple theory is presented in an overly complicated fashion through the use of determinants (and famous Cramer's Rule, or inverse of matrix concept) only because the computation of determinants can be taught and done in a mechanical fashion without much understanding of the concepts. Another added advantage of this complicated approach is that there are some formulas to show (Cramer's rule and inverse of matrix using adjoint). The great disadvantage is that there is no understanding at all and the determinant method simply does not apply in cases where the coefficient matrix is not square or when we have infinitely many solutions.

To sum it up my presentation of this theory serves as an excellent example of the "calculus approach" described here.

Print/PDF Version

0 comments :: The Mysterious Rank (of a Matrix) Demystified

Post a Comment