Last modified on 28 April 2010, at 08:40

Linear Algebra/Gauss' Method/Solutions

SolutionsEdit

This exercise is recommended for all readers.
Problem 1

Use Gauss' method to find the unique solution for each system.

  1. \begin{array}{*{2}{rc}r}
2x  &+  &3y  &=  &13  \\
x   &-  &y   &=  &-1
\end{array}

  2. \begin{array}{*{3}{rc}r}
x   &  &  &-  &z  &=  &0  \\
3x  &+ &y &   &   &=  &1  \\
-x  &+ &y &+  &z  &=  &4
\end{array}
Answer

Gauss' method can be performed in different ways, so these simply exhibit one possible way to get the answer.

  1. Gauss' method
    
\xrightarrow[]{-(1/2)\rho_1+\rho_2}\;
\begin{array}{*{2}{rc}r}
2x  &+  &3y      &=  &13  \\
&-  &(5/2)y  &=  &-15/2              
\end{array}
    gives that the solution is y=3 and x=2.
  2. Gauss' method here
    
\xrightarrow[\rho_1+\rho_3]{-3\rho_1+\rho_2}\;
\begin{array}{*{3}{rc}r}
x   &  &  &-  &z  &=  &0  \\
&  &y &+  &3z &=  &1  \\
&  &y &   &   &=  &4
\end{array}
\;\xrightarrow[]{-\rho_2+\rho_3}\;
\begin{array}{*{3}{rc}r}
x   &  &  &-  &z    &=  &0  \\
&  &y &+  &3z   &=  &1  \\
&  &  &   &-3z  &=  &3
\end{array}
    gives x=-1, y=4, and z=-1.
This exercise is recommended for all readers.
Problem 2

Use Gauss' method to solve each system or conclude "many solutions" or "no solutions".

  1. 
\begin{array}{*{2}{rc}r}
2x  &+  &2y  &=  &5  \\
x  &-  &4y  &=  &0  
\end{array}
  2. 
\begin{array}{*{2}{rc}r}
-x  &+  &y   &=  &1  \\
x  &+  &y   &=  &2  
\end{array}
  3. 
\begin{array}{*{3}{rc}r}
x  &-  &3y  &+  &z  &=  &1  \\
x  &+  &y   &+  &2z &=  &14 
\end{array}
  4. 
\begin{array}{*{2}{rc}r}
-x  &-  &y   &=  &1  \\
-3x  &-  &3y  &=  &2  
\end{array}
  5. 
\begin{array}{*{3}{rc}r}
&   &4y  &+  &z  &=  &20 \\
2x  &-  &2y  &+  &z  &=  &0  \\
x  &   &    &+  &z  &=  &5  \\
x  &+  &y   &-  &z  &=  &10 
\end{array}
  6.  \begin{array}{*{4}{rc}r}
2x  &   &   &+  &z  &+  &w  &=  &5  \\
&   &y  &   &   &-  &w  &=  &-1 \\
3x  &   &   &-  &z  &-  &w  &=  &0  \\
4x  &+  &y  &+  &2z &+  &w  &=  &9  
\end{array}
Answer
  1. Gaussian reduction
    \begin{array}{rcl}
&\xrightarrow[]{-(1/2)\rho_1+\rho_2}
&\begin{array}{*{2}{rc}r}
2x  &+  &2y  &=  &5  \\
&   &-5y &=  &-5/2  
\end{array}
\end{array}
    shows that  y=1/2 and  x=2 is the unique solution.
  2. Gauss' method
    \begin{array}{rcl}
&\xrightarrow[]{\rho_1+\rho_2}
&\begin{array}{*{2}{rc}r}
-x  &+  &y   &=  &1  \\
&   &2y  &=  &3  
\end{array}
\end{array}
    gives  y=3/2 and  x=1/2 as the only solution.
  3. Row reduction
    \begin{array}{rcl}
&\xrightarrow[]{-\rho_1+\rho_2}
&\begin{array}{*{3}{rc}r}
x  &-  &3y  &+  &z  &=  &1  \\
&   &4y  &+  &z  &=  &13 
\end{array}
\end{array}
    shows, because the variable z is not a leading variable in any row, that there are many solutions.
  4. Row reduction
    \begin{array}{rcl}
&\xrightarrow[]{-3\rho_1+\rho_2}
&\begin{array}{*{2}{rc}r}
-x  &-  &y   &=  &1  \\
&   &0   &=  &-1 
\end{array}
\end{array}
    shows that there is no solution.
  5. Gauss' method
    
\xrightarrow[]{\rho_1\leftrightarrow\rho_4}\;
\begin{array}{*{3}{rc}r}
x  &+  &y   &-  &z  &=  &10 \\
2x  &-  &2y  &+  &z  &=  &0  \\
x  &   &    &+  &z  &=  &5  \\
&   &4y  &+  &z  &=  &20 
\end{array}
\;\xrightarrow[-\rho_1+\rho_3]{-2\rho_1+\rho_2}\;
\begin{array}{*{3}{rc}r}
x  &+  &y   &-  &z  &=  &10 \\
&   &-4y &+  &3z &=  &-20\\
&   &-y  &+  &2z &=  &-5 \\
&   &4y  &+  &z  &=  &20 
\end{array}
\;\xrightarrow[\rho_2+\rho_4]{-(1/4)\rho_2+\rho_3}\;
\begin{array}{*{3}{rc}r}
x  &+  &y   &-  &z      &=  &10 \\
&   &-4y &+  &3z     &=  &-20\\
&   &    &   &(5/4)z &=  &0  \\
&   &    &   &4z     &=  &0  
\end{array}
    gives the unique solution  (x,y,z)=(5,5,0) .
  6. Here Gauss' method gives
    
\xrightarrow[-2\rho_1+\rho_4]{-(3/2)\rho_1+\rho_3}\;
\begin{array}{*{4}{rc}r}
2x  &   &   &+  &z       &+  &w       &=  &5  \\
&   &y  &   &        &-  &w       &=  &-1 \\
&   &   &-  &(5/2)z  &-  &(5/2)w  &=  &-15/2  \\
&   &y  &   &        &-  &w       &=  &-1  
\end{array}                                          
\;\xrightarrow[]{-\rho_2+\rho_4}\;
\begin{array}{*{4}{rc}r}
2x  &   &   &+  &z       &+  &w       &=  &5  \\
&   &y  &   &        &-  &w       &=  &-1 \\
&   &   &-  &(5/2)z  &-  &(5/2)w  &=  &-15/2  \\
&   &   &   &        &   &0       &=  &0 
\end{array}
    which shows that there are many solutions.
This exercise is recommended for all readers.
Problem 3

There are methods for solving linear systems other than Gauss' method. One often taught in high school is to solve one of the equations for a variable, then substitute the resulting expression into other equations. That step is repeated until there is an equation with only one variable. From that, the first number in the solution is derived, and then back-substitution can be done. This method takes longer than Gauss' method, since it involves more arithmetic operations, and is also more likely to lead to errors. To illustrate how it can lead to wrong conclusions, we will use the system


\begin{array}{*{2}{rc}r}
x  &+  &3y  &=  &1  \\
2x  &+  &y   &=  &-3 \\
2x  &+  &2y  &=  &0  
\end{array}

from Example 1.12.

  1. Solve the first equation for x and substitute that expression into the second equation. Find the resulting y.
  2. Again solve the first equation for x, but this time substitute that expression into the third equation. Find this y.

What extra step must a user of this method take to avoid erroneously concluding a system has a solution?

Answer
  1. From x=1-3y we get that 2(1-3y)+y=-3, giving y=1.
  2. From x=1-3y we get that 2(1-3y)+2y=0, leading to the conclusion that y=1/2.

Users of this method must check any potential solutions by substituting back into all the equations.

This exercise is recommended for all readers.
Problem 4

For which values of  k are there no solutions, many solutions, or a unique solution to this system?


\begin{array}{*{2}{rc}r}
x  &-  &y  &=  &1  \\
3x  &-  &3y &=  &k  
\end{array}
Answer

Do the reduction

\begin{array}{rcl}
&\xrightarrow[]{-3\rho_1+\rho_2}
&\begin{array}{*{2}{rc}r}
x  &-  &y  &=  &1  \\
&   &0  &=  &-3+k  
\end{array}
\end{array}

to conclude this system has no solutions if  k\neq 3 and if  k=3 then it has infinitely many solutions. It never has a unique solution.

This exercise is recommended for all readers.
Problem 5

This system is not linear, in some sense,


\begin{array}{*{3}{rc}r}
2\sin\alpha  &-  &\cos\beta  &+  &3\tan\gamma  &=  &3  \\
4\sin\alpha  &+  &2\cos\beta &-  &2\tan\gamma  &=  &10  \\
6\sin\alpha  &-  &3\cos\beta &+  &\tan\gamma   &=  &9  
\end{array}

and yet we can nonetheless apply Gauss' method. Do so. Does the system have a solution?

Answer

Let  x=\sin\alpha ,  y=\cos\beta , and  z=\tan\gamma :

\begin{array}{rcl}
\begin{array}{*{3}{rc}r}
2x  &-  &y  &+  &3z  &=  &3  \\
4x  &+  &2y &-  &2z  &=  &10  \\
6x  &-  &3y &+  &z   &=  &9  
\end{array}
&\xrightarrow[-3\rho_1+\rho_3]{-2\rho_1+\rho_2}
&\begin{array}{*{3}{rc}r}
2x  &-  &y  &+  &3z  &=  &3  \\
&   &4y &-  &8z  &=  &4   \\
&   &   &   &-8z &=  &0  
\end{array}
\end{array}

gives  z=0 ,  y=1 , and  x=2 . Note that no  \alpha satisfies that requirement.

This exercise is recommended for all readers.
Problem 6

What conditions must the constants, the b's, satisfy so that each of these systems has a solution? Hint. Apply Gauss' method and see what happens to the right side (Anton 1987).

  1. 
\begin{array}{*{2}{rc}r}
x  &-  &3y  &=  &b_1 \\
3x  &+  &y   &=  &b_2 \\
x  &+  &7y  &=  &b_3 \\
2x  &+  &4y  &=  &b_4 
\end{array}
  2. 
\begin{array}{*{3}{rc}r}
x_1  &+  &2x_2  &+  &3x_3  &=  &b_1  \\
2x_1  &+  &5x_2  &+  &3x_3  &=  &b_2  \\
x_1  &   &      &+  &8x_3  &=  &b_3  
\end{array}
Answer
  1. Gauss' method
    
\xrightarrow[\begin{array}{c}\\[-19pt]\scriptstyle -\rho_1+\rho_3 \\[-5pt]\scriptstyle -2\rho_1+\rho_4\end{array}]{-3\rho_1+\rho_2}\;
\begin{array}{*{2}{rc}r}
x  &-  &3y  &=  &b_1 \\
&   &10y &=  &-3b_1+b_2 \\
&   &10y &=  &-b_1+b_3 \\
&   &10y &=  &-2b_1+b_4 
\end{array}         
\;\xrightarrow[-\rho_2+\rho_4]{-\rho_2+\rho_3}\;
\begin{array}{*{2}{rc}r}
x  &-  &3y  &=  &b_1 \\
&   &10y &=  &-3b_1+b_2 \\
&   &0   &=  &2b_1-b_2+b_3 \\
&   &0   &=  &b_1-b_2+b_4 
\end{array}
    shows that this system is consistent if and only if both  b_3=-2b_1+b_2 and  b_4=-b_1+b_2 .
  2. Reduction
    
\xrightarrow[-\rho_1+\rho_3]{-2\rho_1+\rho_2}\;
\begin{array}{*{3}{rc}r}
x_1  &+  &2x_2  &+  &3x_3  &=  &b_1  \\
&   &x_2   &-  &3x_3  &=  &-2b_1+b_2  \\
&   &-2x_2 &+  &5x_3  &=  &-b_1+b_3  
\end{array}    
\;\xrightarrow[]{2\rho_2+\rho_3}\;
\begin{array}{*{3}{rc}r}
x_1  &+  &2x_2  &+  &3x_3  &=  &b_1  \\
&   &x_2   &-  &3x_3  &=  &-2b_1+b_2  \\
&   &      &   &-x_3  &=  &-5b_1++2b_2+b_3  
\end{array}
    shows that each of  b_1 ,  b_2 , and  b_3 can be any real number— this system always has a unique solution.
Problem 7

True or false: a system with more unknowns than equations has at least one solution. (As always, to say "true" you must prove it, while to say "false" you must produce a counterexample.)

Answer

This system with more unknowns than equations


\begin{array}{*{3}{rc}r}
x  &+  &y  &+  &z  &=  &0  \\
x  &+  &y  &+  &z  &=  &1  
\end{array}

has no solution.

Problem 8

Must any Chemistry problem like the one that starts this subsection— a balance the reaction problem— have infinitely many solutions?

Answer

Yes. For example, the fact that the same reaction can be performed in two different flasks shows that twice any solution is another, different, solution (if a physical reaction occurs then there must be at least one nonzero solution).

This exercise is recommended for all readers.
Problem 9

Find the coefficients  a ,  b , and  c so that the graph of  f(x)=ax^2+bx+c passes through the points  (1,2) ,  (-1,6) , and  (2,3) .

Answer

Because  f(1)=2 ,  f(-1)=6 , and  f(2)=3 we get a linear system.


\begin{array}{*{3}{rc}r}
1a  &+  &1b  &+  &c  &=  &2  \\
1a  &-  &1b  &+  &c  &=  &6  \\
4a  &+  &2b  &+  &c  &=  &3  
\end{array}

Gauss' method

\begin{array}{rcl}
\xrightarrow[-4\rho_1+\rho_2]{-\rho_1+\rho_2}\;
\begin{array}{*{3}{rc}r}
a  &+  &b  &+  &c  &=  &2  \\
&   &-2b&   &   &=  &4  \\
&   &-2b&-  &3c &=  &-5 
\end{array}               
&\xrightarrow[]{-\rho_2+\rho_3}
&\begin{array}{*{3}{rc}r}
a  &+  &b  &+  &c  &=  &2  \\
&   &-2b&   &   &=  &4  \\
&   &   &   &-3c&=  &-9 
\end{array}
\end{array}

shows that the solution is  f(x)=1x^2-2x+3 .

Problem 10

Gauss' method works by combining the equations in a system to make new equations.

  1. Can the equation  3x-2y=5 be derived, by a sequence of Gaussian reduction steps, from the equations in this system?
    
\begin{array}{*{2}{rc}r}
x  &+  &y  &=  &1  \\
4x  &-  &y  &=  &6
\end{array}
  2. Can the equation  5x-3y=2 be derived, by a sequence of Gaussian reduction steps, from the equations in this system?
    
\begin{array}{*{2}{rc}r}
2x  &+  &2y &=  &5  \\
3x  &+  &y  &=  &4
\end{array}
  3. Can the equation  6x-9y+5z=-2 be derived, by a sequence of Gaussian reduction steps, from the equations in the system?
    
\begin{array}{*{3}{rc}r}
2x  &+  &y  &-  &z  &=  &4  \\
6x  &-  &3y &+  &z  &=  &5
\end{array}
Answer
  1. Yes, by inspection the given equation results from  -\rho_1+\rho_2 .
  2. No. The given equation is satisfied by the pair  (1,1) . However, that pair does not satisfy the first equation in the system.
  3. Yes. To see if the given row is  c_1\rho_1+c_2\rho_2 , solve the system of equations relating the coefficients of x, y, z, and the constants:
    
\begin{array}{*{2}{rc}r}
2c_1  &+  &6c_2  &=  &6  \\
c_1  &-  &3c_2  &=  &-9 \\
-c_1  &+  &c_2   &=  &5  \\
4c_1  &+  &5c_2  &=  &-2 
\end{array}
    and get c_1=-3 and c_2=2, so the given row is  -3\rho_1+2\rho_2 .
Problem 11

Prove that, where  a,b,\ldots,e are real numbers and  a\neq 0 , if


ax+by=c

has the same solution set as


ax+dy=e

then they are the same equation. What if  a=0 ?

Answer

If  a\neq 0 then the solution set of the first equation is  \{(x,y)\,\big|\, x=(c-by)/a\} . Taking y=0 gives the solution (c/a,0), and since the second equation is supposed to have the same solution set, substituting into it gives that a(c/a)+d\cdot 0=e, so c=e. Then taking y=1 in x=(c-by)/a gives that a((c-b)/a)+d\cdot 1=e, which gives that b=d. Hence they are the same equation.

When  a=0 the equations can be different and still have the same solution set: e.g.,  0x+3y=6 and  0x+6y=12 .

This exercise is recommended for all readers.
Problem 12

Show that if  ad-bc\neq 0 then


\begin{array}{*{2}{rc}r}
ax  &+  &by  &=  &j  \\
cx  &+  &dy  &=  &k  
\end{array}

has a unique solution.

Answer

We take three cases: that a\neq 0, that a=0 and c\neq 0, and that both a=0 and c=0.

For the first, we assume that  a\neq 0 . Then the reduction

\begin{array}{rcl}
&\xrightarrow[]{-(c/a)\rho_1+\rho_2}
&\begin{array}{*{2}{rc}r}
ax  &+  &by                  &=  &j  \\
&   &(-\frac{cb}{a}+d)y  &=  &-\frac{cj}{a}+k   
\end{array}
\end{array}

shows that this system has a unique solution if and only if  -(cb/a)+d\neq 0   ; remember that  a\neq 0 so that back substitution yields a unique  x (observe, by the way, that  j and  k play no role in the conclusion that there is a unique solution, although if there is a unique solution then they contribute to its value). But  -(cb/a)+d = (ad-bc)/a and a fraction is not equal to  0 if and only if its numerator is not equal to  0 . Thus, in this first case, there is a unique solution if and only if ad-bc\neq 0.

In the second case, if  a=0 but  c\neq 0 , then we swap


\begin{array}{*{2}{rc}r}
cx  &+  &dy  &=  &k  \\
&   &by  &=  &j  
\end{array}

to conclude that the system has a unique solution if and only if  b\neq 0 (we use the case assumption that  c\neq 0 to get a unique  x in back substitution). But— where  a=0 and  c\neq 0 — the condition " b\neq 0 " is equivalent to the condition " ad-bc\neq 0 ". That finishes the second case.

Finally, for the third case, if both  a and  c are  0 then the system


\begin{array}{*{2}{rc}r}
0x  &+  &by  &=  &j  \\
0x  &+  &dy  &=  &k  
\end{array}

might have no solutions (if the second equation is not a multiple of the first) or it might have infinitely many solutions (if the second equation is a multiple of the first then for each  y satisfying both equations, any pair  (x,y) will do), but it never has a unique solution. Note that  a=0 and  c=0 gives that  ad-bc=0 .

This exercise is recommended for all readers.
Problem 13

In the system


\begin{array}{*{2}{rc}r}
ax  &+  &by  &=  &c  \\
dx  &+  &ey  &=  &f  
\end{array}

each of the equations describes a line in the  xy -plane. By geometrical reasoning, show that there are three possibilities: there is a unique solution, there is no solution, and there are infinitely many solutions.

Answer

Recall that if a pair of lines share two distinct points then they are the same line. That's because two points determine a line, so these two points determine each of the two lines, and so they are the same line.

Thus the lines can share one point (giving a unique solution), share no points (giving no solutions), or share at least two points (which makes them the same line).

Problem 14

Finish the proof of Theorem 1.4.

Answer

For the reduction operation of multiplying \rho_i by a nonzero real number k, we have that  (s_1,\ldots,s_n) satisfies this system


\begin{array}{*{4}{rc}r}
a_{1,1}x_1  &+  &a_{1,2}x_2 &+  &\cdots  &+  &a_{1,n}x_n  &=  &d_1  \\
&   &           &   &        &   &            &\vdots   \\
ka_{i,1}x_1  &+  &ka_{i,2}x_2 &+  &\cdots  &+  &ka_{i,n}x_n
&=  &kd_i  \\
&   &           &   &        &   &            &\vdots   \\
a_{m,1}x_1  &+  &a_{m,2}x_2 &+  &\cdots  &+  &a_{m,n}x_n  &=  &d_m  
\end{array}

if and only if

\begin{array}{rl}
a_{1,1}s_1+a_{1,2}s_2+\cdots+a_{1,n}s_n
&=d_1                                              \\
&\vdots                                     \\
\text{and } ka_{i,1}s_1+ka_{i,2}s_2+\cdots+ka_{i,n}s_n
&=kd_i                                              \\
&\vdots                                      \\
\text{and } a_{m,1}s_1+a_{m,2}s_2+\cdots+a_{m,n}s_n
&=d_m
\end{array}

by the definition of "satisfies". But, because  k\neq 0 , that's true if and only if

\begin{array}{rl}
a_{1,1}s_1+a_{1,2}s_2+\cdots+a_{1,n}s_n
&=d_1                                              \\
&\vdots                                     \\
\text{and } a_{i,1}s_1+a_{i,2}s_2+\cdots+a_{i,n}s_n
&=d_i                                              \\
&\vdots                                      \\
\text{and } a_{m,1}s_1+a_{m,2}s_2+\cdots+a_{m,n}s_n
&=d_m
\end{array}

(this is straightforward cancelling on both sides of the i-th equation), which says that  (s_1,\ldots,s_n) solves


\begin{array}{*{4}{rc}r}
a_{1,1}x_1  &+  &a_{1,2}x_2 &+  &\cdots  &+  &a_{1,n}x_n  &=  &d_1  \\
&   &           &   &        &   &            &\vdots   \\
a_{i,1}x_1  &+  &a_{i,2}x_2 &+  &\cdots  &+  &a_{i,n}x_n  &=  &d_i  \\
&   &           &   &        &   &            &\vdots   \\
a_{m,1}x_1  &+  &a_{m,2}x_2 &+  &\cdots  &+  &a_{m,n}x_n  &=
&d_m  
\end{array}

as required.

For the pivot operation k\rho_i+\rho_j, we have that  (s_1,\ldots,s_n) satisfies


\begin{array}{*{4}{rc}r}
a_{1,1}x_1             &+  &\cdots  &+  &a_{1,n}x_n  &=  &d_1 \\
&   &        &   &            &\vdots   \\
a_{i,1}x_1             &+  &\cdots  &+  &a_{i,n}x_n  &=  &d_i \\
&   &        &   &            &\vdots   \\
(ka_{i,1}+a_{j,1})x_1  &+  &\cdots  &+  &(ka_{i,n}+a_{j,n})x_n
&=  &kd_i+d_j  \\
&   &        &   &            &\vdots   \\
a_{m,1}x_1             &+   &\cdots  &+  &a_{m,n}x_n  &=  
&d_m 
\end{array}

if and only if

\begin{array}{rl}
a_{1,1}s_1+\cdots+a_{1,n}s_n
&=d_1                                              \\
&\vdots                                     \\
\text{and } a_{i,1}s_1+\cdots+a_{i,n}s_n
&=d_i                                              \\
&\vdots                                      \\
\text{and } (ka_{i,1}+a_{j,1})s_1+\cdots+(ka_{i,n}+a_{j,n})s_n
&=kd_i+d_j                                              \\
&\vdots                                      \\
\text{and } a_{m,1}s_1+a_{m,2}s_2+\cdots+a_{m,n}s_n
&=d_m
\end{array}

again by the definition of "satisfies". Subtract  k times the  i -th equation from the  j -th equation (remark: here is where  i\neq j is needed; if  i=j then the two  d_i 's above are not equal) to get that the previous compound statement holds if and only if

\begin{array}{rl}
a_{1,1}s_1+\cdots+a_{1,n}s_n
&=d_1                                              \\
&\vdots                                     \\
\text{and } a_{i,1}s_1+\cdots+a_{i,n}s_n
&=d_i                                              \\
&\vdots                                      \\
\text{and } (ka_{i,1}+a_{j,1})s_1+\cdots+(ka_{i,n}+a_{j,n})s_n \\
\quad-(ka_{i,1}s_1+\cdots+ka_{i,n}s_n)
&=kd_i+d_j-kd_i                                    \\
&\vdots                                      \\
\text{and } a_{m,1}s_1+\cdots+a_{m,n}s_n
&=d_m
\end{array}

which, after cancellation, says that  (s_1,\ldots,s_n) solves


\begin{array}{*{4}{rc}r}
a_{1,1}x_1  &+   &\cdots  &+  &a_{1,n}x_n  &=  &d_1  \\
&    &        &   &            &\vdots   \\
a_{i,1}x_1  &+   &\cdots  &+  &a_{i,n}x_n  &=  &d_i  \\
&    &        &   &            &\vdots   \\
a_{j,1}x_1  &+  &\cdots  &+  &a_{j,n}x_n  &=  &d_j  \\
&   &        &   &            &\vdots   \\
a_{m,1}x_1  &+  &\cdots  &+  &a_{m,n}x_n  &=
&d_m
\end{array}

as required.

Problem 15

Is there a two-unknowns linear system whose solution set is all of  \mathbb{R}^2 ?

Answer

Yes, this one-equation system:


0x+0y=0

is satisfied by every  (x,y)\in\mathbb{R}^2 .

This exercise is recommended for all readers.
Problem 16

Are any of the operations used in Gauss' method redundant? That is, can any of the operations be synthesized from the others?

Answer

Yes. This sequence of operations swaps rows  i and  j


\xrightarrow[]{\rho_i+\rho_j}\quad
\xrightarrow[]{-\rho_j+\rho_i}\quad
\xrightarrow[]{\rho_i+\rho_j}\quad
\xrightarrow[]{-1\rho_i}

so the row-swap operation is redundant in the presence of the other two.

Problem 17

Prove that each operation of Gauss' method is reversible. That is, show that if two systems are related by a row operation S_1\rightarrow S_2 then there is a row operation to go back S_2\rightarrow S_1.

Answer

Swapping rows is reversed by swapping back.

\begin{array}{rcl}
\begin{array}{*{3}{rc}r}
a_{1,1}x_1  &+  &\cdots  &+  &a_{1,n}x_n  &=  &d_1  \\
&   &        &   &            &\vdots   \\
a_{m,1}x_1  &+  &\cdots  &+  &a_{m,n}x_n  &=  &d_m  
\end{array}
&\xrightarrow[]{\rho_i\leftrightarrow\rho_j}\;
\xrightarrow[]{\rho_j\leftrightarrow\rho_i}
&\begin{array}{*{3}{rc}r}
a_{1,1}x_1  &+  &\cdots  &+  &a_{1,n}x_n  &=  &d_1  \\
&   &        &   &            &\vdots   \\
a_{m,1}x_1  &+  &\cdots  &+  &a_{m,n}x_n  &=  &d_m  
\end{array}
\end{array}

Multiplying both sides of a row by  k\neq 0  is reversed by dividing by  k .

\begin{array}{rcl}
\begin{array}{*{3}{rc}r}
a_{1,1}x_1  &+  &\cdots  &+  &a_{1,n}x_n  &=  &d_1  \\
&   &        &   &            &\vdots   \\
a_{m,1}x_1  &+  &\cdots  &+  &a_{m,n}x_n  &=  &d_m  
\end{array}
&\xrightarrow[]{k\rho_i}\;
\xrightarrow[]{(1/k)\rho_i}
&\begin{array}{*{3}{rc}r}
a_{1,1}x_1  &+  &\cdots  &+  &a_{1,n}x_n  &=  &d_1  \\
&   &        &   &            &\vdots   \\
a_{m,1}x_1  &+  &\cdots  &+  &a_{m,n}x_n  &=  &d_m  
\end{array}
\end{array}

Adding  k times a row to another is reversed by adding  -k times that row.

\begin{array}{rcl}
\begin{array}{*{3}{rc}r}
a_{1,1}x_1  &+  &\cdots  &+  &a_{1,n}x_n  &=  &d_1  \\
&   &        &   &            &\vdots   \\
a_{m,1}x_1  &+  &\cdots  &+  &a_{m,n}x_n  &=  &d_m  
\end{array}
&\xrightarrow[]{k\rho_i+\rho_j}\;
\xrightarrow[]{-k\rho_i+\rho_j}
&\begin{array}{*{3}{rc}r}
a_{1,1}x_1  &+  &\cdots  &+  &a_{1,n}x_n  &=  &d_1  \\
&   &        &   &            &\vdots   \\
a_{m,1}x_1  &+  &\cdots  &+  &a_{m,n}x_n  &=  &d_m 
\end{array}
\end{array}

Remark: observe for the third case that if we were to allow  i=j then the result wouldn't hold.


\begin{array}{*{2}{rc}r}
3x  &+  &2y  &=  &7  
\end{array}
\;\xrightarrow[]{2\rho_1+\rho_1}\;
\begin{array}{*{2}{rc}r}
9x  &+  &6y  &=  &21 
\end{array}                 
\;\xrightarrow[]{-2\rho_1+\rho_1}\;
\begin{array}{*{2}{rc}r}
-9x  &-  &6y  &=  &-21 
\end{array}
? Problem 18

A box holding pennies, nickels and dimes contains thirteen coins with a total value of  83 cents. How many coins of each type are in the box? (Anton 1987)

Answer

Let  p ,  n , and  d be the number of pennies, nickels, and dimes. For variables that are real numbers, this system

\begin{array}{rcl}
\begin{array}{*{3}{rc}r}
p  &+ &n   &+  &d   &=  &13   \\
p  &+ &5n  &+  &10d &=  &83    
\end{array}
&\xrightarrow[]{-\rho_1+\rho_2}
&\begin{array}{*{3}{rc}r}
p  &+ &n   &+  &d   &=  &13   \\
&  &4n  &+  &9d  &=  &70    
\end{array}
\end{array}

has infinitely many solutions. However, it has a limited number of solutions in which  p ,  n , and  d are non-negative integers. Running through  d=0 , ...,  d=8 shows that  (p,n,d)=(3,4,6) is the only sensible solution.

? Problem 19

Four positive integers are given. Select any three of the integers, find their arithmetic average, and add this result to the fourth integer. Thus the numbers 29, 23, 21, and 17 are obtained. One of the original integers is:

  1. 19
  2. 21
  3. 23
  4. 29
  5. 17

(Salkind 1975, 1955 problem 38)

Answer

Solving the system


\begin{array}{*{2}{rc}r}
(1/3)(a+b+c)  &+  &d  &=  &29  \\
(1/3)(b+c+d)  &+  &a  &=  &23  \\
(1/3)(c+d+a)  &+  &b  &=  &21  \\
(1/3)(d+a+b)  &+  &c  &=  &17
\end{array}

we obtain a=12, b=9, c=3, d=21. Thus the second item, 21, is the correct answer.

This exercise is recommended for all readers.
? Problem 20

Laugh at this:  \mbox{AHAHA}+\mbox{TEHE}=\mbox{TEHAW} . It resulted from substituting a code letter for each digit of a simple example in addition, and it is required to identify the letters and prove the solution unique (Ransom & Gupta 1935).

Answer

This is how the answer was given in the cited source.

A comparison of the units and hundreds columns of this addition shows that there must be a carry from the tens column. The tens column then tells us that  A<H , so there can be no carry from the units or hundreds columns. The five columns then give the following five equations.

\begin{array}{rl}
A+E  &=  W  \\
2H   &=  A+10  \\
H    &=  W+1  \\
H+T  &=  E+10  \\
A+1  &=  T
\end{array}

The five linear equations in five unknowns, if solved simultaneously, produce the unique solution:  A=4 ,  T=5 ,  H=7 ,  W=6 and  E=2 , so that the original example in addition was  47474+5272=52746 .

? Problem 21

The Wohascum County Board of Commissioners, which has 20 members, recently had to elect a President. There were three candidates (A, B, and C); on each ballot the three candidates were to be listed in order of preference, with no abstentions. It was found that 11 members, a majority, preferred A over B (thus the other 9 preferred B over A). Similarly, it was found that 12 members preferred C over A. Given these results, it was suggested that B should withdraw, to enable a runoff election between A and C. However, B protested, and it was then found that 14 members preferred B over C! The Board has not yet recovered from the resulting confusion. Given that every possible order of A, B, C appeared on at least one ballot, how many members voted for B as their first choice (Gilbert, Krusemeyer & Larson 1993, Problem number 2)?

Answer

This is how the answer was given in the cited source.

Eight commissioners voted for B. To see this, we will use the given information to study how many voters chose each order of A, B, C.

The six orders of preference are ABC, ACB, BAC, BCA, CAB, CBA; assume they receive a, b, c, d, e, f votes respectively. We know that


\begin{array}{*{3}{rc}r}
a  &+  &b  &+  &e  &=  &11  \\
d  &+  &e  &+  &f  &=  &12  \\
a  &+  &c  &+  &d  &=  &14
\end{array}

from the number preferring A over B, the number preferring C over A, and the number preferring B over C. Because 20 votes were cast, we also know that


\begin{array}{*{3}{rc}r}
c  &+  &d  &+  &f  &=  &9  \\
a  &+  &b  &+  &c  &=  &8  \\
b  &+  &e  &+  &f  &=  &6
\end{array}

from the preferences for B over A, for A over C, and for C over B.

The solution is a=6, b=1, c=1, d=7, e=4, and f=1. The number of commissioners voting for B as their first choice is therefore c+d=1+7=8.

Comments. The answer to this question would have been the same had we known only that at least 14 commissioners preferred B over C.

The seemingly paradoxical nature of the commissioners's preferences (A is preferred to B, and B is preferred to C, and C is preferred to A), an example of "non-transitive dominance", is not uncommon when individual choices are pooled.

? Problem 22

"This system of  n linear equations with  n unknowns," said the Great Mathematician, "has a curious property."

"Good heavens!" said the Poor Nut, "What is it?"

"Note," said the Great Mathematician, "that the constants are in arithmetic progression."

"It's all so clear when you explain it!" said the Poor Nut. "Do you mean like  6x+9y=12 and  15x+18y=21 ?"

"Quite so," said the Great Mathematician, pulling out his bassoon. "Indeed, the system has a unique solution. Can you find it?"

"Good heavens!" cried the Poor Nut, "I am baffled."

Are you? (Dudley, Lebow & Rothman 1963)

Answer

This is how the answer was given in the cited source.

We have not used "dependent" yet; it means here that Gauss' method shows that there is not a unique solution. If  n\geq 3 the system is dependent and the solution is not unique. Hence  n<3 . But the term "system" implies  n>1 . Hence  n=2 . If the equations are


\begin{array}{*{2}{rc}r}
ax  &+ &(a+d)y  &=  &a+2d  \\
(a+3d)x  &+ &(a+4d)y &=  &a+5d  
\end{array}

then  x=-1 ,  y=2 .

ReferencesEdit

  • Anton, Howard (1987), Elementary Linear Algebra, John Wiley & Sons .
  • Dudley, Underwood (proposer); Lebow, Arnold (proposer); Rothman, David (solver) (Jan. 1963), "Elemantary problem 1151", American Mathematical Monthly 70 (1): 93 .
  • Gilbert, George T.; Krusemeyer, Mark; Larson, Loren C. (1993), The Wohascum County Problem Book, The Mathematical Association of America .
  • Ransom, W. R. (proposer); Gupta, Hansraj (solver) (Jan. 1935), "Elementary problem 105", American Mathematical Monthly 42 (1): 47 .
  • Salkind, Charles T. (1975), Contest Problem Book No 1: Annual High School Mathematics Examinations 1950-1960 .