Systems of linear equations. Matrix solution, augmented matrix, homogeneous and non-homogeneous systems, Cramer�s rule, null space

SolitaryRoad.com

Website owner:  James Miller

[ Home ] [ Up ] [ Info ] [ Mail ]

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

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.

Proof.

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], x₄ = 0. Let x₃= a where a is arbitrary; then x₁= 10 + 11a and x₂ = -2 - 4a. The solution of the system is given by x₁ = 10 + 11a , x₂ = -2 - 4a , x₃ = a, x₄ = 0 or

Homogeneous and non-homogeneous systems. A linear equation of the type

a₁x₁ + a₂x₂ + .... + a_nx_n = 0

in which the constant term is zero is called homogeneous whereas a linear equation of the type

a₁x₁ + a₂x₂ + .... + a_nx_n = 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 |A| ≠0.

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 A_i, (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 X₁, X₂, ... ,X_s 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 u₁, u₂, ... , u_n-r that span the null space of A. Thus the complete solution can be written as

X = c₁u₁ + c₂u₂ + .... + c_n-ru_n-r

where c₁, c₂, ... , c_n-r 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 u₁, u₂, ... , u_n-rthat span the null space of A. If we denote a particular solution of AX = B by x_p then the complete solution can be written as

X = x_p + c₁u₁ + c₂u₂ + .... + c_n-ru_n-r

where c₁, c₂, ... , c_n-r are arbitrary constants.

References.

Ayres. Matrix Theory.