Linear Systems of Equations

Blake's Newton

Back

A linear equation system is a collection of coefficients (aij), variables (xi) and constants (di) of the following kind:

a11x1 + a12x2 + ..... + a1nxn = d1
a21x1 + a22x2 + ..... + a2nxn = d2
...............................................
an1x1 + an2x2 + ..... + annxn = dn

This can be rewritten in matrix form:

Ax = d

where:

é a11 a12 .... a1n ù
A = ê a21 a22 .... a2n ú
  ê .... .... .... .... ú
ë an1 an2 .... ann û

is the matrix of coefficients and:

 

  é x1 ù
x = ê x2 ú
  ê ... ú
  ë xn û

is the vector of variables or unknowns, while:

  é d1 ù
d = ê d2 ú
  ê ... ú
  ë dn û

is the vector of constants.

Defining the "augmented" matrix [A, d] as an n ´ (n+1) matrix with d in the last column, it can be shown that there exists a solution x to the system Ax = d if and only if rank is such that r(A) = r([A, d]). The system has no solution if r(A) < r[A, d]. This is obvious as d ought to be a linear combination of the elements in A if a solution x to exist.

If r(A) = r([A, d]) = n, then the solution is unique (thus if A is non-singular, then Ax = d has a unique solution, x). If r(A) = r([A, d]) < n, then the solution is not unique - in fact, there will be an infinite number of solutions. Consider the following:

Theorem: If Ax = d has more than one solution, then it has an infinite number of solutions.

Proof: Suppose x* and x** are two solutions to the system Ax = d. Then, for any scalar a ¹ 0, we know that a Ax* = a d and (1-a )Ax** = (1-a )d, so A[a x* + (1-a )x**] = d, thus the constructed vector a x* + (1-a )x** is also a solution. As this is true for all a ¹ 0, then there are an infinite number of such vectors.§

Thus a system, Ax = d has either no solution, a unique solution, or an infinite number of solutions. If A is a square matrix and non-singular (has no linearly dependent rows/columns, i.e. |A| ¹ 0), then we can solve for the unique solution vector x*.

(1) Inverting

The straightforward procedure is by inverting the matrix:

Ax = d Þ x* = A-1d

where A-1 is the inverse of A and expressed as: A-1 = (adj A)/|A|, where adj A is the adjoint matrix of A (defined as the transpose of a matrix whose elements are the cofactors of the corresponding elements in A) while |A| is the determinant of A.

(2) Cramer's Rule

A more practical procedure is to consider the following:

xi* = |Ai|/|A|

where |Ai| is the determinant of matrix A with the ith column replaced by the solution vector d. So, for x1:

ê d1 a12 .... a1n ú
|A1| = ê d2 a22 .... a2n ú
  ê .... .... .... .... ú
ê dn an2 .... ann ú

We can do this for all xi, i = 1, ..., n and thus obtain the solution vector x*.

(3) Homogeneous Systems

If it turns out that d = 0 for our earlier system of equations, i.e. Ax = 0, then we have a homogeneous system. This causes a problem in solving for x. In fact, there are only two alternatives: either we have the trivial solution x = 0 or else x is indeterminate.

We can see triviality immediately from Cramer's rule. As xi = |Ai|/|A|, then because the system is homogeneous, the vector 0 is in the ith column of Ai. Thus, expanding by that column, xi = 0/|A| = 0. This will be true for all i = 1, ..., n, thus every xi = 0. The only alternative to the trivial case is if it also happens to be the case that |A| = 0, so then xi = 0/0 which is indeterminate, i.e. there are infinite number of solutions for xi.

However, we can still say something about x in the homogeneous case. Namely, if we have indeterminacy (i.e. if |A| = 0), we can still sometimes obtain proportional values xi/xj for every i, j = 1, .., n even though we cannot obtain xi and xj directly.  But for this we need to analyze eigenvalues.

 

back Back top Top Selected References

nextNext

 

 

top1.gif (924 bytes)Top
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

All rights reserved, Gonçalo L. Fonseca