Let and be matrices (over a field) having dimension and , respectively, such that is in reduced row echelon form. Compute the solutions of the matrix equation . In particular, note the following.
- If, for some , the th row of is zero and the th row of is nonzero, then no solution exists.
- Every solution to may be constructed by choosing the rows of corresponding to nonpivotal columns of arbitrarily, as the remaining rows are then determined uniquely.
Use this result to characterize the solutions of when is not in reduced row echelon form.
Suppose that for some , the th row of is zero while the th row of is nonzero. Suppose is a solution to the equation . Choose such that the entry of is nonzero. (This exists by our hypothesis.) By the definition of matrix multiplication, this entry is obtained by multiplying the th row of by the th column of ; since the th row of is zero, we have a contradiction. Thus has no solutions.
Suppose now that for all , the th row of is zero only if the th row of is also zero. We will now construct all the solutions of the equation recursively. Note that if , then by the previous argument, has no solution if . We assume now that .
For the base case, suppose has one row. Let and be arbitrary matrices (so that dimensions work) and let . Letting , we see that . Conversely, if is any solution to this equation, we see that has this form.
For the inductive step, suppose and write . Choose arbitrarily (so that the dimensions work), let be any solution of the equation and let . Again letting , we see that . Conversely, if is any such solution, then has this form.
Now let and be arbitrary matrices (so that dimensions work). By this previous exercise, is row equivalent to a matrix in reduced row echelon form. That is, there exists a reduced row echelon matrix and an invertible matrix such that . Now , so that if and only if .
Note that this allows us to solve arbitrary “linear equations in one variable” over matrices. A similar proof involving column equivalence (rather than row equivalence) could be used to give an analogous solution for linear equations of the form . In the future, we will see how canonical forms of matrices can be used to find matrix solutions to polynomial equations of higher degree.