Problem Post 2-3: EROs Should be Taught in High School

Problem Posts

[Level 1-2]

Disclaimer: I'm using this problem to prove a point, that is, that it's feasible, and easy to teach elementary row operations, (in particular in conjunction with Gauss-Jordan Elimination) at the high school level (at the very least for contest-involved students). While central to linear algebra, Gaussian elimination can be appreciated at a fundamental capacity. Essentially it's just a way of manipulating numbers, no different from right-to-left addition or long division.

The main point, I believe, in introducing students to GJ, is to demonstrate that any system of $n$ linear equations and $n$ unknowns can be solved (i.e. all solutions, one or infinite, found) quite uncreatively.

If you want to know how to solve the problem, the solution is at the bottom of the article.

QUESTION
(16th PMO Orals) Suppose that $w+4x+9y+16z=6$, $4w+9x+16y+25z=7$, $9w+16x+25y+36z=12$. Find $w+x+y+z$.

Okay, so we're given a system of three equations in four variables. Basic high school algebra tells us that there may be infinitely many or zero solutions, but certainly if a solution exists, it's not unique.

So for clarity let's write that system down again:
\[
\begin{cases}
w+4x+9y+16z=6\\
4w+9x+16y+25z=7\\
9w+16x+25y+36z=12
\end{cases}
\]
Nobody wants to write $w$, $x$, and so on all over again. Even if we leave out these variables we still know what we're talking about, so let's get rid of them, and write things in an augmented matrix.
\[
\left( \begin{array}{cccc|c}1 & 4 & 9 & 16 & 6\\
4 & 9 & 16 & 25 & 7\\
9 & 16 & 25 & 36 & 12
\end{array}\right)
\]
The first column represents coefficients of $w$, the second coefficients of $x$, and so on. See how much time we save if we just keep organized?

So if you remember how to solve equations, what we should do now is subtract multiples of one equation from another, so that variables are eliminated. In our augmented matrix notation this is the same as subtracting multiples of one row from another, for example:
\[
\left( \begin{array}{cccc|c}1 & 4 & 9 & 16 & 6\\
4 & 9 & 16 & 25 & 7\\
9 & 16 & 25 & 36 & 12
\end{array}\right)\xrightarrow{R_{2}-4R_{1}}\left( \begin{array}{cccc|c}1 & 4 & 9 & 16 & 6\\
0 & -7 & -20 & -39 & -17\\
9 & 16 & 25 & 36 & 12
\end{array}\right)
\]
where we subtract four times of equation (or row) 1 from equation (or row) 2.

Now let's do that again, but this time, between rows 1 and 3:

\[
\left( \begin{array}{cccc|c}1 & 4 & 9 & 16 & 6\\
0 & -7 & -20 & -39 & -17\\
9 & 16 & 25 & 36 & 12
\end{array}\right)\xrightarrow{R_{3}-9R_{1}}\left( \begin{array}{cccc|c}1 & 4 & 9 & 16 & 6\\
0 & -7 & -20 & -39 & -17\\
0 & -20 & -56 & -108 & -42
\end{array}\right)
\]
The new equation 2 reads, $-7x-20y-39z=-17$, which looks ugly, so let's divide both sides of the new equation 2 by $-7$. This shows up in the matrix like this:
\[
\left( \begin{array}{cccc|c}1 & 4 & 9 & 16 & 6\\
0 & -7 & -20 & -39 & -17\\
0 & -20 & -56 & -108 & -42
\end{array}\right)\xrightarrow{-\frac{1}{7}R_{2}}\left( \begin{array}{cccc|c}1 & 4 & 9 & 16 & 6\\
0 & 1 & \frac{20}{7} & \frac{39}{7} & \frac{17}{7}\\
0 & -20 & -56 & -108 & -42
\end{array}\right)
\]
Now time to get rid of $x$ in the third row:
\[
\left( \begin{array}{cccc|c}1 & 4 & 9 & 16 & 6\\
0 & 1 & \frac{20}{7} & \frac{39}{7} & \frac{17}{7}\\
0 & -20 & -56 & -108 & -42
\end{array}\right)\xrightarrow{R_{3}+20R_{2}}\left( \begin{array}{cccc|c}1 & 4 & 9 & 16 & 6\\
0 & 1 & \frac{20}{7} & \frac{39}{7} & \frac{17}{7}\\
0 & 0 & \frac{8}{7} & \frac{24}{7} & \frac{46}{7}
\end{array}\right)
\]
Then multiply row 3 by $7/8$:
\[
\left( \begin{array}{cccc|c}1 & 4 & 9 & 16 & 6\\
0 & 1 & \frac{20}{7} & \frac{39}{7} & \frac{17}{7}\\
0 & 0 & \frac{8}{7} & \frac{24}{7} & \frac{46}{7}
\end{array}\right)\xrightarrow{\frac{7}{8}R_{3}}\left( \begin{array}{cccc|c}1 & 4 & 9 & 16 & 6\\
0 & 1 & \frac{20}{7} & \frac{39}{7} & \frac{17}{7}\\
0 & 0 & 1 & 3 & \frac{23}{4}
\end{array}\right)
\]
Now we can use row 3 to 'kill' the coefficients in column 3:
\[
\left( \begin{array}{cccc|c}1 & 4 & 9 & 16 & 6\\
0 & 1 & \frac{20}{7} & \frac{39}{7} & \frac{17}{7}\\
0 & 0 & 1 & 3 & \frac{23}{4}
\end{array}\right)\xrightarrow[R_{1}-9R_{3}]{R_{2}-\frac{20}{7}R_{3}}\left( \begin{array}{cccc|c}1 & 4 & 0 & -11 & -\frac{183}{4}\\
0 & 1 & 0 & -3 & -14\\
0 & 0 & 1 & 3 & \frac{23}{4}
\end{array}\right)
\]
Then finally use row 2 to kill the coefficient in row 1:

\[
\left( \begin{array}{cccc|c}1 & 4 & 0 & -11 & -\frac{183}{4}\\
0 & 1 & 0 & -3 & -14\\
0 & 0 & 1 & 3 & \frac{23}{4}
\end{array}\right)\xrightarrow{R_{1}-4R_{2}}\left( \begin{array}{cccc|c}1 & 0 & 0 & 1 & \frac{41}{4}\\
0 & 1 & 0 & -3 & -14\\
0 & 0 & 1 & 3 & \frac{23}{4}
\end{array}\right)
\]
Converting back to equation form, we have
\[
\begin{cases}
w+z=\frac{41}{4}\\
x+-3z=-14\\
y+3z=\frac{23}{4}
\end{cases}
\]
It's pretty clear that we have infinitely many solutions; give the value of $z$ and the other values simply follow. Imagine having to do that writing all the variable names and the plus symbols!

GAUSS-JORDAN ELIMINATION
There are two kinds of operations we did on the matrix. Along with a third operation (swapping rows), these three are called elementary row operations. They have the special property that they don't destroy any of the information given by the original system of equations; that is, the ending matrix is saying 100% of what the original matrix is saying, only much more clearly.

Moreover, the way in which we're implementing the operations, systematically isolating the coefficients, is called Gauss-Jordan Elimination. It runs on exactly the same principle as the usual thing taught in high school, only more systematic.

SOLUTION 1
We write the augmented matrix
\[
\left( \begin{array}{cccc|c}1 & 4 & 9 & 16 & 6\\
4 & 9 & 16 & 25 & 7\\
9 & 16 & 25 & 36 & 12
\end{array}\right)
\]
and perform Gauss Jordan elimination, ending with
\[
\left( \begin{array}{cccc|c}1 & 0 & 0 & 1 & \frac{41}{4}\\
0 & 1 & 0 & -3 & -14\\
0 & 0 & 1 & 3 & \frac{23}{4}
\end{array}\right)
\]
Now we simply get $w+x+y+z=w+z+x-3z+y+3z=\frac{41}{4}-14+\frac{23}{4}=\boxed{2}$.

This isn't hard, just tedious.

But, you argue, this is an oral round question, shouldn't there be an faster way to do it? Well yes - and you can be even faster with augmented matrices!

So again let's start with
\[
\left( \begin{array}{cccc|c}1 & 4 & 9 & 16 & 6\\
4 & 9 & 16 & 25 & 7\\
9 & 16 & 25 & 36 & 12
\end{array}\right)
\]
Note that the first four columns all have perfect square entries. Now what we want to get here is $w+x+y+z=\text{something}$, or essentially the row $\left( \begin{array}{cccc|c}1 & 1 & 1 & 1 & \square\end{array}\right)$. How do we do this by combining multiple of the three rows above?

Well, note that the $i^{\mathrm{th}}$ column has entries $i^{2}$, $\left(i+1\right)^{2}$, and $\left(i+2\right)^{2}$. What can we do with this? Well, there's the sly identity $\left(i+2\right)^{2}+i^{2}-2\left(i+1\right)^{2}=2$, so to make that work for us, we add row 3 and $-2$ times row 2 to row 1:
\[
\left( \begin{array}{cccc|c}1 & 4 & 9 & 16 & 6\\
4 & 9 & 16 & 25 & 7\\
9 & 16 & 25 & 36 & 12
\end{array}\right)\xrightarrow[R_{1}+R_{3}]{R_{1}-2R_{2}}\left( \begin{array}{cccc|c}2 & 2 & 2 & 2 & 4\\
4 & 9 & 16 & 25 & 7\\
9 & 16 & 25 & 36 & 12
\end{array}\right)\xrightarrow{\frac{1}{2}R_{1}}\left( \begin{array}{cccc|c}1 & 1 & 1 & 1 & 2\\
4 & 9 & 16 & 25 & 7\\
9 & 16 & 25 & 36 & 12
\end{array}\right)
\]
and we're done.

SOLUTION 2
Leveraging the identity $\left(x+2\right)^{2}+x^{2}-2\left(x+1\right)^{2}=2$, we add equation 3 and $-2$ times equation 2 to equation 1, giving us $2w+2x+2y+2z=4$. Hence our answer is $\boxed{2}$.