A linear equation system is a collection of coefficients (a_{ij}), variables (x_{i}) and constants (d_{i}) of the following kind:
a_{11}x_{1} + a_{12}x_{2} + ..... + a_{1n}x_{n} = d_{1}
a_{21}x_{1} + a_{22}x_{2} + ..... + a_{2n}x_{n} = d_{2}
...............................................
a_{n1}x_{1} + a_{n2}x_{2} + ..... + a_{nn}x_{n} = d_{n}
This can be rewritten in matrix form:
Ax = d
where:
a_{11} | a_{12} | .... | a_{1n} | |
a_{21} | a_{22} | .... | a_{2n} | |
A = | .... | .... | .... | .... |
a_{n1} | a_{n2} | .... | a_{nn} |
is the matrix of coefficients and:
x_{1} | |
x = | x_{2} |
... | |
x_{n} |
is the vector of variables or unknowns, while:
d_{1} | |
d = | d_{2} |
... | |
d_{n} |
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^{-1}d
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.
A more practical procedure is to consider the following:
x_{i}* = |A_{i}|/|A|
where |A_{i}| is the determinant of matrix A with the ith column replaced by the solution vector d. So, for x_{1}:
d_{1} | a_{12} | .... | a_{1n} | |
d_{2} | a_{22} | .... | a_{2n} | |
A_{1} = | .... | .... | .... | .... |
d_{n} | a_{n2} | .... | a_{nn} |
We can do this for all x_{i}, i = 1, ..., n and thus obtain the solution vector x*.
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 x_{i} = |A_{i}|/|A|, then because the system is homogeneous, the vector 0 is in the ith column of A_{i}. Thus, expanding by that column, x_{i} = 0/|A| = 0. This will be true for all i = 1, ..., n, thus every x_{i} = 0. The only alternative to the trivial case is if it also happens to be the case that |A| = 0, so then x_{i} = 0/0 which is indeterminate, i.e. there are infinite number of solutions for x_{i}.
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 x_{i}/x_{j} for every i, j = 1, .., n even though we cannot obtain x_{i} and x_{j} directly. But for this we need to analyze eigenvalues.
Back | Top | Selected References | Next |