Comprehensive Study Notes

To deal with the kind of variation function discussed in the next section, we need to know about simultaneous linear equations.

Consider the following system of $n$ linear equations in $n$ unknowns:

\(
\begin{align}
& a{11} x{1}+a{12} x{2}+\cdots+a{1 n} x{n}=b{1} \
& a{21} x{1}+a{22} x{2}+\cdots+a{2 n} x{n}=b{2} \
& \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \tag{8.35}\
& a{n 1} x{1}+a{n 2} x{2}+\cdots+a{n n} x{n}=b_{n}
\end{align}
\)

where the $a$ 's and $b$ 's are known constants and $x{1}, x{2}, \ldots, x{n}$ are the unknowns. If at least one of the $b$ 's is not zero, we have a system of inhomogeneous linear equations. Such a system can be solved by Cramer's rule. (For a proof of Cramer's rule, see Sokolnikoff and Redheffer, p. 708.) Let $\operatorname{det}\left(a{i j}\right)$ be the determinant of the coefficients of the unknowns in (8.35). Cramer's rule states that $x_{k}(k=1,2, \ldots, n)$ is given by

\(
x{k}=\frac{\left|\begin{array}{cccccccc}
a{11} & a{12} & \ldots & a{1, k-1} & b{1} & a{1, k+1} & \ldots & a{1 n} \tag{8.36}\
a{21} & a{22} & \ldots & a{2, k-1} & b{2} & a{2, k+1} & \ldots & a{2 n} \
\cdot & \cdot & \ldots & \cdot & \cdot & \cdot & \ldots & \cdot \
a{n 1} & a{n 2} & \ldots & a{n, k-1} & b{n} & a{n, k+1} & \ldots & a{n n}
\end{array}\right|}{\operatorname{det}\left(a{i j}\right)}, k=1,2, \ldots, n
\)

where $\operatorname{det}\left(a{i j}\right)$ is given by (8.20) and the numerator is the determinant obtained by replacing the $k$ th column of $\operatorname{det}\left(a{i j}\right)$ with the elements $b{1}, b{2}, \ldots, b_{n}$. Although Cramer's rule is
of theoretical significance, it should not be used for numerical calculations, since successive elimination of unknowns is much more efficient.

A widely used successive-elimination procedure is Gaussian elimination, which proceeds as follows: Divide the first equation in (8.35) by the coefficient $a{11}$ of $x{1}$, thereby making the coefficient of $x{1}$ equal to 1 in this equation. Then subtract $a{21}$ times the first equation from the second equation, subtract $a{31}$ times the first equation from the third equation, $\ldots$, and subtract $a{n 1}$ times the first equation from the $n$th equation. This eliminates $x{1}$ from all equations but the first. Now divide the second equation by the coefficient of $x{2}$; then subtract appropriate multiples of the second equation from the 3 rd, 4 th, $\ldots$, $n$th equations, so as to eliminate $x{2}$ from all equations but the first and second. Continue in this manner. Ultimately, equation $n$ will contain only $x{n}$, equation $n-1$ only $x{n-1}$ and $x{n}$, and so on. The value of $x{n}$ found from equation $n$ is substituted into equation $n-1$ to give $x{n-1}$; the values of $x{n}$ and $x{n-1}$ are substituted into equation $n-2$ to give $x_{n-2}$; and so on. If at any stage a coefficient we want to divide by happens to be zero, the equation with the zero coefficient is exchanged with a later equation that has a nonzero coefficient in the desired position. (The Gaussian elimination procedure also gives an efficient way to evaluate a determinant; see Prob. 8.25.)

A related method is Gauss-Jordan elimination, which proceeds the same way as Gaussian elimination, except that instead of eliminating $x{2}$ from equations $3,4, \ldots, n$, we eliminate $x{2}$ from equations $1,3,4, \ldots, n$, by subtracting appropriate multiples of the second equation from equations $1,3,4, \ldots, n$; instead of eliminating $x{3}$ from equations $4,5, \ldots, n$, we eliminate $x{3}$ from equations $1,2,4,5, \ldots, n$; and so on. At the end of Gauss-Jordan elimination, equation 1 contains only $x{1}$, equation 2 contains only $x{2}, \ldots$, equation $n$ contains only $x_{n}$. Gauss-Jordan elimination requires more computation than Gaussian elimination.

If all the $b$ 's in (8.35) are zero, we have a system of linear homogeneous equations:

\(
\begin{align}
& a{11} x{1}+a{12} x{2}+\cdots+a{1 n} x{n}=0 \
& a{21} x{1}+a{22} x{2}+\cdots+a{2 n} x{n}=0 \
& \cdot \cdot \cdot \cdot \cdot \cdots \cdot \cdot \cdot \tag{8.37}\
& a{n 1} x{1}+a{n 2} x{2}+\cdots+a{n n} x{n}=0
\end{align}
\)

One obvious solution of (8.37) is $x{1}=x{2}=\cdots=x{n}=0$, which is called the trivial solution. If the determinant of the coefficients in (8.37) is not equal to zero, $\operatorname{det}\left(a{i j}\right) \neq 0$, then we can use Cramer's rule (8.36) to solve for the unknowns, and we find $x{k}=0, k=1,2, \ldots, n$, since the determinant in the numerator of (8.36) has a column all of whose elements are zero. Thus, when $\operatorname{det}\left(a{i j}\right) \neq 0$, the only solution is the trivial solution, which is of no interest. For there to be a nontrivial solution of a system of $n$ linear homogeneous equations in $n$ unknowns, the determinant of the coefficients must be zero. Also, this condition can be shown to be sufficient to ensure the existence of a nontrivial solution. We thus have the extremely important theorem:

A system of $n$ linear homogeneous equations in $n$ unknowns has a nontrivial solution if and only if the determinant of the coefficients is zero.

Suppose that $\operatorname{det}\left(a{i j}\right)=0$, so that (8.37) has a nontrivial solution. How do we find it? With $\operatorname{det}\left(a{i j}\right)=0$, Cramer's rule (8.36) gives $x{k}=0 / 0, k=1, \ldots, n$, which is indeterminate. Thus Cramer's rule is of no immediate help. We also observe that, if $x{1}=d{1}, x{2}=d{2}, \ldots$, $x{n}=d{n}$ is a solution of (8.37), then so is $x{1}=c d{1}, x{2}=c d{2}, \ldots, x{n}=c d_{n}$, where $c$ is an arbitrary constant. This is easily seen, since

\(
a{11} c d{1}+a{12} c d{2}+\cdots+a{1 n} c d{n}=c\left(a{11} d{1}+a{12} d{2}+\cdots+a{1 n} d{n}\right)=c \cdot 0=0
\)

and so on. Therefore, the solution to the linear homogeneous system of equations will contain an arbitrary constant, and we cannot determine a unique value for each unknown. To solve (8.37), we therefore assign an arbitrary value to any one of the unknowns, say $x{n}$; we set $x{n}=c$, where $c$ is an arbitrary constant. Having assigned a value to $x_{n}$, we transfer the last term in each of the equations of (8.37) to the right side to get

\(
\begin{gather}
a{11} x{1}+a{12} x{2}+\cdots+a{1, n-1} x{n-1}=-a{1, n} c \
a{21} x{1}+a{22} x{2}+\cdots+a{2, n-1} x{n-1}=-a{2, n} c \tag{8.38}\
\cdot \cdot \cdot \
a{n-1,1} x{1}+a{n-1,2} x{2}+\cdots+a{n-1, n-1} x{n-1}=-a{n-1, n} c \
a{n 1} x{1}+a{n 2} x{2}+\cdots+a{n, n-1} x{n-1}=-a{n n} c
\end{gather}
\)

We now have $n$ equations in $n-1$ unknowns, which is one more equation than we need. We therefore discard any one of the equations of (8.38), say the last one. This gives a system of $n-1$ linear inhomogeneous equations in $n-1$ unknowns. We could then apply Cramer's rule (8.36) to solve for $x{1}, x{2}, \ldots, x_{n-1}$. Since the constants on the right side of the equations in (8.38) all contain the factor $c$, Theorem IV in Section 8.3 shows that all the unknowns contain this arbitrary constant as a factor. The form of the solution is therefore

\(
\begin{equation}
x{1}=c e{1}, \quad x{2}=c e{2}, \quad \ldots, \quad x{n-1}=c e{n-1}, \quad x_{n}=c \tag{8.39}
\end{equation}
\)

where $e{1}, \ldots, e{n-1}$ are numbers and $c$ is an arbitrary constant.

EXAMPLE

Solve

\(
\begin{aligned}
& 3 x{1}+4 x{2}+x{3}=0 \
& x{1}+3 x{2}-2 x{3}=0 \
& x{1}-2 x{2}+5 x_{3}=0
\end{aligned}
\)

This is a set of linear homogeneous equations, and we begin by evaluating the determinant of the coefficients. We find (see the Exercise)

\(
\left|\begin{array}{rrr}
3 & 4 & 1 \
1 & 3 & -2 \
1 & -2 & 5
\end{array}\right|=0
\)

Therefore, a nontrivial solution exists. We set $x{3}$ equal to an arbitrary constant $c$ ( $x{3}=c$ ) and discard the third equation to give

\(
\begin{aligned}
3 x{1}+4 x{2} & =-c \
x{1}+3 x{2} & =2 c
\end{aligned}
\)

Subtracting 3 times the second equation from the first, we get $-5 x{2}=-7 c$, so $x{2}=\frac{7}{5} c$. Substitution into $x{1}+3 x{2}=2 c$ gives $x{1}+\frac{21}{5} c=2 c$, so $x{1}=-\frac{11}{5} c$. Hence the general solution is $x{1}=-\frac{11}{5} c, x{2}=\frac{7}{5} c, x{3}=c$. For those allergic to fractions, we define a new arbitrary constant $s$ as $s \equiv \frac{1}{5} c$ and write $x{1}=-11 s, x{2}=7 s, x{3}=5 s$.

EXERCISE (a) Verify that the coefficient determinant in this example is zero. (b) Verify that the third equation in this example can be obtained by adding a certain constant times the second equation to the first equation.

The procedure just outlined fails if the determinant of the inhomogeneous system of $n-1$ equations in $n-1$ unknowns [(8.38) with the last equation omitted] happens to be zero. Cramer's rule then has a zero in the denominator and is of no use. We could try to get around this difficulty by initially assigning the arbitrary value to another of the unknowns rather than to $x_{n}$. We could also try discarding some other equation of (8.38), rather than the last one. What we are looking for is a nonvanishing determinant of order $n-1$ formed from the determinant of the coefficients of the system (8.37) by striking out a row and a column. If such a determinant exists, then by the procedure given, with the right choice of the equation to be discarded and the right choice of the unknown to be assigned an arbitrary value, we can solve the system and will get solutions of the form (8.39). If no such determinant exists, we must assign arbitrary values to two of the unknowns and attempt to proceed from there. Thus the solution to (8.37) might contain two (or even more) arbitrary constants.

An efficient way to solve a system of linear homogeneous equations is to do GaussJordan elimination on the equations. If only the trivial solution exists, the final set of equations obtained will be $x{1}=0, x{2}=0, \ldots, x_{n}=0$. If a nontrivial solution exists, at least one equation will be reduced to the form $0=0$; if $m$ equations of the form $0=0$ are obtained, we assign arbitrary constants to $m$ of the unknowns and express the remaining unknowns in terms of these $m$ unknowns.

EXAMPLE

Use Gauss-Jordan elimination to solve the set of equations in the preceding example.
In doing Gaussian or Gauss-Jordan elimination on a set of $n$ inhomogeneous or homogeneous equations, we can eliminate needless writing by omitting the variables $x{1}, \ldots, x{n}$ and writing down only the $n$-row, $(n+1)$-column array of coefficients and constant terms (including any zero coefficients); we then produce the next array by operating on the numbers of each row as if that row were the equation it represents.
To eliminate one set of divisions, we interchange the first and second equations so that we start with $a_{11}=1$. Detaching the coefficients and proceeding with GaussJordan elimination, we have

The first array is the original set of equations with the first and second equations interchanged. To eliminate $x{1}$ from the second and third equations, we subtract 3 times row one from row two and 1 times row one from row three, thereby producing the second array. Division of row two by -5 produces the third array. To eliminate $x{2}$ from the first and third equations, we subtract 3 times row two from row one and -5 times row two from row three, thereby producing the fourth array. Because the fourth array has the $x{3}$ coefficient in row three equal to zero, we cannot use row three to eliminate $x{3}$ from rows one and two (as would be the last step in the GaussJordan algorithm). Discarding the last equation, which reads $0=0$, we assign $x{3}=k$, where $k$ is an arbitrary constant. The first and second equations in the last array read $x{1}+\frac{11}{5} x{3}=0$ and $x{2}-\frac{7}{5} x{3}=0$, or $x{1}=-\frac{11}{5} x{3}, x{2}=\frac{7}{5} x{3}$. The general solution is $x{1}=-\frac{11}{5} k, x{2}=\frac{7}{5} k, x{3}=k$.