Solvability of systems of linear equations

Systems of linear equations: System of linear equations and matrices

Solvability of systems of linear equations

Using the concept of rank for a matrix, we can characterize the solvability of a system of linear equations. First a definition of the key concept:

Rank The rank of a matrix is the number of non-zero rows in an echelon form of the matrix. We denote the rank of a matrix \(A\) by \(\text{rank}(A)\).

The number of non-zero rows in an echelon form of a matrix does not depend on the echelon form. This can be seen by observing that

this number does not change when the echelon form is further reduced to a reduced echelon form;
the reduced echelon form is unique, so the rank is unique in the case of a reduced echelon form.

The rank of a matrix is, by definition, not greater than the number of rows. But also the rank is not greater than the number of columns. After all, the number of rows having a leading element equal to #1# in the reduced echelon form is in fact no greater than the number of columns.

Rank criteria for the existence of solutions of systems of linear equations

A system of linear equations is inconsistent if and only if the rank of the coefficient matrix is smaller than the rank of the augmented matrix.
If a system of #m# linear equations in #n# unknowns has a solution, then the solution is parameterized by \(n-r\) free parameters, where \(r\) the rank is of the associated coefficient matrix.

In the definition of rank, and consequently in the above theorem, we deliberately used the echelon form and did not require that the matrix be in reduced echelon form. The latter form is not always necessary to determine solvability of a linear system of equations.

Bringing the augmented matrix to reduced echelon form does not change the rank of the augmented matrix, the rank of the coefficient matrix or the solution. We may therefore assume that the augmented matrix is in reduced echelon form. The corresponding coefficient matrix then has that form as well. The rank of a matrix in reduced echelon form is equal to the number of rows with a leading element #1#.

1. The rank of the coefficient matrix is smaller than the rank of the augmented matrix is and only if the augmented matrix has a row with a leading element #1# in the last column. In this case (and only then) will the equation corresponding to that row be equal to #0=1#, so that the system is inconsistent.

2. The role of the rank #r# is the same as in solutions of systems of linear equations. The statement follows immediately from that theorem.

3. This statement follows from the previous two because by statement 1 there is a solution and by statement 2 there are no free parameters.

For homogeneous systems we already know that there is always a solution:

Nontrivial solutions of homogeneous systems Each homogeneous system has a trivial solution in which all the values of the unknowns are equal to zero. A nonzero solution of a homogeneous system is called a nontrivial solution.

Each homogeneous system of linear equations having more unknowns than equations, possesses nontrivial solutions.

Apply the Gauss elimination method to such a system. The number of bound unknowns (the rank of the system) is at most equal to the number of equations. Because the number of unknowns is larger than the number of equations, there must be free parameters. By assigning one of these variables a nonzero value, we get a nonzero solution.

Determine the rank of the matrix \[A=\matrix{1 & 1 & 4 & -4 \\ 1 & 2 & 5 & -3 \\ 2 & 3 & 9 & -7 \\ }\]

#\text{rang}(A)=# #2#

Via elementary row operations we reduce the matrix to the reduced echelon form \[ \begin{array}{rcl}A = \matrix{1&1&4&-4\\1&2&5&-3\\2&3&9&-7\\}&\sim\matrix{1&1&4&-4\\0&1&1&1\\2&3&9&-7\\}&{\blue{\begin{array}{c}\phantom{x} R_2-R_1\phantom{x}\end{array}}}\\&\sim\matrix{1&1&4&-4\\0&1&1&1\\0&1&1&1\\}&{\blue{\begin{array}{c}\phantom{x} R_3-2R_1\end{array}}}\\&\sim\matrix{1&0&3&-5\\0&1&1&1\\0&1&1&1\\}&{\blue{\begin{array}{c}R_1-R_2\phantom{x}\end{array}}}\\&\sim\matrix{1&0&3&-5\\0&1&1&1\\0&0&0&0\\}&{\blue{\begin{array}{c}\phantom{x} R_3-R_2\end{array}}}\end{array}\]
Because the rank is the number of non-null rows of this matrix, we conclude that the rank of the matrix #A# equals #2#.

In the worked-out solution, we have reduced the matrix #A# to the reduced echelon form, while it is sufficient to reduce #A# to an echelon form.

New example