Website owner: James Miller
Systems of linear equations. Matrix solution, augmented matrix, homogeneous and non-homogeneous systems, Cramer’s rule, null space
Matrix form of a linear system of equations. The matrix form of a system of m linear equations in n unknowns
is
or, more concisely,
AX = B
where A is the coefficient matrix,
and
.
Augmented matrix of a system of linear equations. The augmented matrix of a system of linear equations AX = B is the matrix
formed by appending the constant vector (b’s) to the right of the coefficient matrix.
Solving a system of linear equations by reducing the augmented matrix of the system to row canonical form. A system of linear equations AX = B can be solved by reducing the augmented matrix of the system to row canonical form by elementary row operations.
Example. Solve the system
The augmented matrix is
[A B] is reduced by elementary row transformations to row equivalent canonical form as follows:
Thus the solution is the equivalent system of equations:
Expressed in vector form, we have
Basic Theorems
How does one know if a system of m linear equations in n unknowns is consistent or inconsistent i.e. if it has a solution or not? The answer is given by the following fundamental theorem.
Fundamental theorem. A system AX = B of m linear equations in n unknowns is consistent if and only if the coefficient matrix and the augmented matrix of the system have the same rank.
Corollary. A necessary condition for the system AX = B of n + 1 linear equations in n unknowns to have a solution is that |A B| = 0 i.e. the determinant of the augmented matrix equals zero.
Theorem. In a consistent system AX = B of m linear equations in n unknowns of rank r < n, n-r of the unknowns may be chosen so that the coefficient matrix of the remaining r unknowns is of rank r. When these n-r unknowns are assigned any whatever values, the other r unknowns are uniquely determined.
Example. In the system
the augmented matrix is
We reduce [A B] by elementary row transformations to row equivalent canonical form [C K] as follows:
Since A and [A B] are each of rank r = 3, the given system is consistent; moreover, the general
solution contains n - r = 4 - 3 = 1 arbitrary constant. From the last row of [C K],
= 0. Let
= a where a is arbitrary; then
= 10 + 11a and
= -2 - 4a.. The solution of the system is
given by
= 10 + 11a ,
= -2 - 4a ,
= a,
= 0 or
Homogeneous and non-homogeneous systems. A linear equation of the type
= 0
in which the constant term is zero is called homogeneous whereas a linear equation of the type
= b
where the constant term b is not zero is called non-homogeneous. Similarly a system of equations AX = 0 is called homogeneous and a system AX = B is called non-homogeneous provided B is not the zero vector.
Theorem. A system of n non-homogeneous equations in n unknowns AX = B has a unique
solution provided the rank of its coefficient matrix A is n, that is provided
.
Two additional methods for solving a consistent non-homogeneous system AX = B of n equations in n unknowns.
Method of determinants using Cramers’s Rule. Denote by
, (i = 1,2, ..., n) the matrix
obtained from A by replacing its i-th column with the column of constants (the b’s). Then, if |A|
0, the system AX = B has the unique solution
Solution using A-1 . If |A|
0 , A-1 exists and the solution of the system AX = B is given by X
= A-1 B.
Theorem. In a system of n linear equations in n unknowns AX = B, if the determinant of the coefficient matrix A is zero, no solution can exist unless all the determinants which appear in the numerators in Cramer’s Rule are also zero.
Homogeneous systems of equations.
Consider the homogeneous system of linear equations AX = 0 consisting of m equations in n unknowns. Let the rank of the coefficient matrix A be r. If r = n the solution consists of only the single solution X = 0, which is called the trivial solution. If r < n there are an infinite number of solution vectors which will satisfy the system corresponding to all points in some subspace of n-dimensional space. To illustrate this let us consider some simple examples from ordinary three-dimensional space.
Suppose the system AX = 0 consists of the single equation
5x + 3y + 9z = 0
This equation corresponds to a plane in three-dimensional space that passes through the origin of the coordinate system. Any point on this plane satisfies the equation and is thus a solution to our system AX = 0. The set of all solutions to our system AX = 0 corresponds to all points on this plane. Furthermore, since the plane passes through the origin of the coordinate system, the plane represents a vector space. Why? Because a linear combination of any two vectors in the plane is also in the plane and any vector in the plane can be obtained as a linear combination of any two basis vectors in the plane. So, in summary, in this particular example the solution set to our system AX = 0 corresponds to the two-dimensional subspace of three-dimensional space represented by this plane. We call this subspace the solution space of the system AX = 0.
Let us consider another example. Suppose the system AX = 0 consists of the following two equations
2x + 5y + 3z = 0
9x - 2y - 8z = 0
These two equations correspond to two planes in three-dimensional space that intersect in some line which passes through the origin of the coordinate system. Any point of this line of intersection satisfies the system and is thus a solution to our system AX = 0. Furthermore, since the line passes through the origin of the coordinate system, the line represents a vector space. A linear combination of any two vectors in the line is also in the line and any vector in the line can be obtained as a linear combination of any basis vector for the line. So, in summary, in this example the solution set to our system AX = 0 corresponds to a one-dimensional subspace of three-dimensional space represented by this line of intersection of the two planes. In this case the solution space of the system AX = 0 is one-dimensional.
What determines the dimension of the solution space of the system AX = 0? The dimension is given by n - r. In our first example the number of unknowns, n, is 3 and the rank, r, is 1 so the dimension of the solution space was 3 - 1 = 2. In our second example n = 3 and r = 2 so the dimension of the solution space was 3 - 2 = 1.
Null space of a matrix. The solution space of the homogeneous system AX = 0 is called the null space of matrix A. The reason for this name is that if matrix A is viewed as a linear operator that maps points of some vector space V into itself, it can be viewed as mapping all the elements of this solution space of AX = 0 into the null element "0". Thus the null space N of A is that subspace of all vectors in V which are imaged into the null element “0" by the matrix A.
Nullity of a matrix. The nullity of a matrix A is the dimension of the null space of A.
If matrix A has nullity s, then AX = 0 has s linearly independent solutions X1, X2, ... ,Xs such that every solution of AX = 0 is a linear combination of them and every linear combination of them is a solution. A basis for the null space A is any set of s linearly independent solutions of AX = 0. The nullity of an mxn matrix A of rank r is given by
s = n - r .
Theorem 1. A necessary and sufficient condition for the system AX = 0 to have a solution other than the trivial solution is that the rank of A be r < n.
Theorem 2. A necessary and sufficient condition that a system AX = 0 of n homogeneous equations in unknowns have a solution other than the trivial solution is |A| = 0.
Theorem 3. If the rank of AX = 0 is r < n, the system has exactly n-r linearly independent solutions such that every solution is a linear combination of these n-r linearly independent solutions and every such linear combination is a solution.
Complete solution of the homogeneous system AX = 0.
The complete solution of the linear system AX = 0 of m equations in n unknowns consists of the
null space of A which can be given as all linear combinations of any set of linearly independent
vectors which spans this null space. If the rank of A is r, there will be n-r linearly independent
vectors
that span the null space of A. Thus the complete solution can be
written as
X =
where
are arbitrary constants.
Complete solution of the non-homogeneous system AX = B.
If the system AX = B of m equations in n unknowns is consistent, a complete solution of the
system is given by the complete solution of AX = 0 plus any particular solution of AX = B. The
complete solution of AX = 0 consists of the null space of A which can be given as all linear
combinations of any set of linearly independent vectors which spans this null space. If the rank
of A is r, there will be n-r linearly independent vectors
that span the null space
of A. If we denote a particular solution of AX = B by
then the complete solution can be
written as
X =
+
where
are arbitrary constants.
References.
Ayres. Matrix Theory.