Linear Algebra/Gauss-Jordan Reduction/Solutions

Problem 1

Use Gauss-Jordan reduction to solve each system.

1. ${\displaystyle {\begin{array}{*{2}{rc}r}x&+&y&=&2\\x&-&y&=&0\end{array}}}$
2. ${\displaystyle {\begin{array}{*{3}{rc}r}x&&&-&z&=&4\\2x&+&2y&&&=&1\end{array}}}$
3. ${\displaystyle {\begin{array}{*{2}{rc}r}3x&-&2y&=&1\\6x&+&y&=&1/2\end{array}}}$
4. ${\displaystyle {\begin{array}{*{3}{rc}r}2x&-&y&&&=&-1\\x&+&3y&-&z&=&5\\&&y&+&2z&=&5\end{array}}}$

Answer

These answers show only the Gauss-Jordan reduction. With it, describing the solution set is easy.

1. ${\displaystyle \left({\begin{array}{*{2}{c}|c}1&1&2\\1&-1&0\end{array}}\right){\xrightarrow[{}]{-\rho _{1}+\rho _{2}}}\left({\begin{array}{*{2}{c}|c}1&1&2\\0&-2&-2\end{array}}\right){\xrightarrow[{}]{-(1/2)\rho _{2}}}\left({\begin{array}{*{2}{c}|c}1&1&2\\0&1&1\end{array}}\right){\xrightarrow[{}]{-\rho _{2}+\rho _{1}}}\left({\begin{array}{*{2}{c}|c}1&0&1\\0&1&1\end{array}}\right)}$
2. ${\displaystyle \left({\begin{array}{*{3}{c}|c}1&0&-1&4\\2&2&0&1\end{array}}\right){\xrightarrow[{}]{-2\rho _{1}+\rho _{2}}}\left({\begin{array}{*{3}{c}|c}1&0&-1&4\\0&2&2&-7\end{array}}\right){\xrightarrow[{}]{(1/2)\rho _{2}}}\left({\begin{array}{*{3}{c}|c}1&0&-1&4\\0&1&1&-7/2\end{array}}\right)}$

3. ${\displaystyle \left({\begin{array}{*{2}{c}|c}3&-2&1\\6&1&1/2\end{array}}\right){\xrightarrow[{}]{-2\rho _{1}+\rho _{2}}}\left({\begin{array}{*{2}{c}|c}3&-2&1\\0&5&-3/2\end{array}}\right){\xrightarrow[{(1/5)\rho _{2}}]{(1/3)\rho _{1}}}\left({\begin{array}{*{2}{c}|c}1&-2/3&1/3\\0&1&-3/10\end{array}}\right){\xrightarrow[{}]{(2/3)\rho _{2}+\rho _{1}}}\left({\begin{array}{*{2}{c}|c}1&0&2/15\\0&1&-3/10\end{array}}\right)}$

4. A row swap here makes the arithmetic easier.

   ${\displaystyle \left({\begin{array}{*{3}{c}|c}2&-1&0&-1\\1&3&-1&5\\0&1&2&5\end{array}}\right){\xrightarrow[{}]{-(1/2)\rho _{1}+\rho _{2}}}\left({\begin{array}{*{3}{c}|c}2&-1&0&-1\\0&7/2&-1&11/2\\0&1&2&5\end{array}}\right){\xrightarrow[{}]{\rho _{2}\leftrightarrow \rho _{3}}}\left({\begin{array}{*{3}{c}|c}2&-1&0&-1\\0&1&2&5\\0&7/2&-1&11/2\end{array}}\right)}$

   ${\displaystyle {\begin{array}{rl}&{\xrightarrow[{}]{-(7/2)\rho _{2}+\rho _{3}}}\left({\begin{array}{*{3}{c}|c}2&-1&0&-1\\0&1&2&5\\0&0&-8&-12\end{array}}\right){\xrightarrow[{-(1/8)\rho _{2}}]{(1/2)\rho _{1}}}\left({\begin{array}{*{3}{c}|c}1&-1/2&0&-1/2\\0&1&2&5\\0&0&1&3/2\end{array}}\right)\\&{\xrightarrow[{}]{-2\rho _{3}+\rho _{2}}}\left({\begin{array}{*{3}{c}|c}1&-1/2&0&-1/2\\0&1&0&2\\0&0&1&3/2\end{array}}\right){\xrightarrow[{}]{(1/2)\rho _{2}+\rho _{1}}}\left({\begin{array}{*{3}{c}|c}1&0&0&1/2\\0&1&0&2\\0&0&1&3/2\end{array}}\right)\end{array}}}$

Problem 2

Find the reduced echelon form of each matrix.

1. ${\displaystyle {\begin{pmatrix}2&1\\1&3\end{pmatrix}}}$
2. ${\displaystyle {\begin{pmatrix}1&3&1\\2&0&4\\-1&-3&-3\end{pmatrix}}}$
3. ${\displaystyle {\begin{pmatrix}1&0&3&1&2\\1&4&2&1&5\\3&4&8&1&2\end{pmatrix}}}$
4. ${\displaystyle {\begin{pmatrix}0&1&3&2\\0&0&5&6\\1&5&1&5\end{pmatrix}}}$

Answer

Use Gauss-Jordan reduction.

1. ${\displaystyle {\xrightarrow[{}]{-(1/2)\rho _{1}+\rho _{2}}}{\begin{pmatrix}2&1\\0&5/2\end{pmatrix}}{\xrightarrow[{(2/5)\rho _{2}}]{(1/2)\rho _{1}}}{\begin{pmatrix}1&1/2\\0&1\end{pmatrix}}{\xrightarrow[{}]{-(1/2)\rho _{2}+\rho _{1}}}{\begin{pmatrix}1&0\\0&1\end{pmatrix}}}$
2. ${\displaystyle {\xrightarrow[{\rho _{1}+\rho _{3}}]{-2\rho _{1}+\rho _{2}}}{\begin{pmatrix}1&3&1\\0&-6&2\\0&0&-2\end{pmatrix}}{\xrightarrow[{-(1/2)\rho _{3}}]{-(1/6)\rho _{2}}}{\begin{pmatrix}1&3&1\\0&1&-1/3\\0&0&1\end{pmatrix}}{\xrightarrow[{-\rho _{3}+\rho _{1}}]{(1/3)\rho _{3}+\rho _{2}}}{\begin{pmatrix}1&3&0\\0&1&0\\0&0&1\end{pmatrix}}{\xrightarrow[{}]{-3\rho _{2}+\rho _{1}}}{\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}}}$

3. ${\displaystyle {\xrightarrow[{-3\rho _{1}+\rho _{3}}]{-\rho _{1}+\rho _{2}}}{\begin{pmatrix}1&0&3&1&2\\0&4&-1&0&3\\0&4&-1&-2&-4\end{pmatrix}}{\xrightarrow[{}]{-\rho _{2}+\rho _{3}}}{\begin{pmatrix}1&0&3&1&2\\0&4&-1&0&3\\0&0&0&-2&-7\end{pmatrix}}}$

   ${\displaystyle {\xrightarrow[{-(1/2)\rho _{3}}]{(1/4)\rho _{2}}}{\begin{pmatrix}1&0&3&1&2\\0&1&-1/4&0&3/4\\0&0&0&1&7/2\end{pmatrix}}{\xrightarrow[{}]{-\rho _{3}+\rho _{1}}}{\begin{pmatrix}1&0&3&0&-3/2\\0&1&-1/4&0&3/4\\0&0&0&1&7/2\end{pmatrix}}}$

4. ${\displaystyle {\xrightarrow[{}]{\rho _{1}\leftrightarrow \rho _{3}}}{\begin{pmatrix}1&5&1&5\\0&0&5&6\\0&1&3&2\end{pmatrix}}{\xrightarrow[{}]{\rho _{2}\leftrightarrow \rho _{3}}}{\begin{pmatrix}1&5&1&5\\0&1&3&2\\0&0&5&6\end{pmatrix}}{\xrightarrow[{}]{(1/5)\rho _{3}}}{\begin{pmatrix}1&5&1&5\\0&1&3&2\\0&0&1&6/5\end{pmatrix}}}$

   ${\displaystyle {\xrightarrow[{-\rho _{3}+\rho _{1}}]{-3\rho _{3}+\rho _{2}}}{\begin{pmatrix}1&5&0&19/5\\0&1&0&-8/5\\0&0&1&6/5\end{pmatrix}}{\xrightarrow[{}]{-5\rho _{2}+\rho _{1}}}{\begin{pmatrix}1&0&0&59/5\\0&1&0&-8/5\\0&0&1&6/5\end{pmatrix}}}$

Problem 3

Find each solution set by using Gauss-Jordan reduction, then reading off the parametrization.

1. ${\displaystyle {\begin{array}{*{3}{rc}r}2x&+&y&-&z&=&1\\4x&-&y&&&=&3\end{array}}}$
2. ${\displaystyle {\begin{array}{*{4}{rc}r}x&&&-&z&&&=&1\\&&y&+&2z&-&w&=&3\\x&+&2y&+&3z&-&w&=&7\end{array}}}$
3. ${\displaystyle {\begin{array}{*{4}{rc}r}x&-&y&+&z&&&=&0\\&&y&&&+&w&=&0\\3x&-&2y&+&3z&+&w&=&0\\&&-y&&&-&w&=&0\end{array}}}$
4. ${\displaystyle {\begin{array}{*{5}{rc}r}a&+&2b&+&3c&+&d&-&e&=&1\\3a&-&b&+&c&+&d&+&e&=&3\end{array}}}$

Answer

For the "Gauss" halves, see the answers to Problem I.2.5.

1. The "Jordan" half goes this way.

   ${\displaystyle {\xrightarrow[{-(1/3)\rho _{2}}]{(1/2)\rho _{1}}}\left({\begin{array}{*{3}{c}|c}1&1/2&-1/2&1/2\\0&1&-2/3&-1/3\end{array}}\right){\xrightarrow[{}]{-(1/2)\rho _{2}+\rho _{1}}}\left({\begin{array}{*{3}{c}|c}1&0&-1/6&2/3\\0&1&-2/3&-1/3\end{array}}\right)}$

   The solution set is this

   ${\displaystyle \{{\begin{pmatrix}2/3\\-1/3\\0\end{pmatrix}}+{\begin{pmatrix}1/6\\2/3\\1\end{pmatrix}}z\,{\big |}\,z\in \mathbb {R} \}}$

2. The second half is

   ${\displaystyle {\xrightarrow[{}]{\rho _{3}+\rho _{2}}}\left({\begin{array}{*{4}{c}|c}1&0&-1&0&1\\0&1&2&0&3\\0&0&0&1&0\end{array}}\right)}$

   so the solution is this.

   ${\displaystyle \{{\begin{pmatrix}1\\3\\0\\0\end{pmatrix}}+{\begin{pmatrix}1\\-2\\1\\0\end{pmatrix}}z\,{\big |}\,z\in \mathbb {R} \}}$

3. This Jordan half

   ${\displaystyle {\xrightarrow[{}]{\rho _{2}+\rho _{1}}}\left({\begin{array}{*{4}{c}|c}1&0&1&1&0\\0&1&0&1&0\\0&0&0&0&0\\0&0&0&0&0\end{array}}\right)}$

   gives

   ${\displaystyle \{{\begin{pmatrix}0\\0\\0\\0\end{pmatrix}}+{\begin{pmatrix}-1\\0\\1\\0\end{pmatrix}}z+{\begin{pmatrix}-1\\-1\\0\\1\end{pmatrix}}w\,{\big |}\,z,w\in \mathbb {R} \}}$

   (of course, the zero vector could be omitted from the description).
4. The "Jordan" half

   ${\displaystyle {\xrightarrow[{}]{-(1/7)\rho _{2}}}\left({\begin{array}{*{5}{c}|c}1&2&3&1&-1&1\\0&1&8/7&2/7&-4/7&0\end{array}}\right){\xrightarrow[{}]{-2\rho _{2}+\rho _{1}}}\left({\begin{array}{*{5}{c}|c}1&0&5/7&3/7&1/7&1\\0&1&8/7&2/7&-4/7&0\end{array}}\right)}$

   ends with this solution set.

   ${\displaystyle \{{\begin{pmatrix}1\\0\\0\\0\\0\end{pmatrix}}+{\begin{pmatrix}-5/7\\-8/7\\1\\0\\0\end{pmatrix}}c+{\begin{pmatrix}-3/7\\-2/7\\0\\1\\0\end{pmatrix}}d+{\begin{pmatrix}-1/7\\4/7\\0\\0\\1\end{pmatrix}}e\,{\big |}\,c,d,e\in \mathbb {R} \}}$

Problem 4

Give two distinct echelon form versions of this matrix.

${\displaystyle {\begin{pmatrix}2&1&1&3\\6&4&1&2\\1&5&1&5\end{pmatrix}}}$

Answer

Routine Gauss' method gives one:

${\displaystyle {\xrightarrow[{-(1/2)\rho _{1}+\rho _{3}}]{-3\rho _{1}+\rho _{2}}}{\begin{pmatrix}2&1&1&3\\0&1&-2&-7\\0&9/2&1/2&7/2\end{pmatrix}}{\xrightarrow[{}]{-(9/2)\rho _{2}+\rho _{3}}}{\begin{pmatrix}2&1&1&3\\0&1&-2&-7\\0&0&19/2&35\end{pmatrix}}}$

and any cosmetic change, like multiplying the bottom row by ${\displaystyle 2}$,

${\displaystyle {\begin{pmatrix}2&1&1&3\\0&1&-2&-7\\0&0&19&70\end{pmatrix}}}$

gives another.

Problem 5

List the reduced echelon forms possible for each size.

1. ${\displaystyle 2\!\times \!2}$
2. ${\displaystyle 2\!\times \!3}$
3. ${\displaystyle 3\!\times \!2}$
4. ${\displaystyle 3\!\times \!3}$

Answer

In the cases listed below, we take ${\displaystyle a,b\in \mathbb {R} }$. Thus, some canonical forms listed below actually include infinitely many cases. In particular, they includes the cases ${\displaystyle a=0}$ and ${\displaystyle b=0}$.

1. ${\displaystyle {\begin{pmatrix}0&0\\0&0\end{pmatrix}}}$, ${\displaystyle {\begin{pmatrix}1&a\\0&0\end{pmatrix}}}$, ${\displaystyle {\begin{pmatrix}0&1\\0&0\end{pmatrix}}}$, ${\displaystyle {\begin{pmatrix}1&0\\0&1\end{pmatrix}}}$
2. ${\displaystyle {\begin{pmatrix}0&0&0\\0&0&0\end{pmatrix}}}$, ${\displaystyle {\begin{pmatrix}1&a&b\\0&0&0\end{pmatrix}}}$, ${\displaystyle {\begin{pmatrix}0&1&a\\0&0&0\end{pmatrix}}}$, ${\displaystyle {\begin{pmatrix}0&0&1\\0&0&0\end{pmatrix}}}$, ${\displaystyle {\begin{pmatrix}1&0&a\\0&1&b\end{pmatrix}}}$, ${\displaystyle {\begin{pmatrix}1&a&0\\0&0&1\end{pmatrix}}}$, ${\displaystyle {\begin{pmatrix}0&1&0\\0&0&1\end{pmatrix}}}$
3. ${\displaystyle {\begin{pmatrix}0&0\\0&0\\0&0\end{pmatrix}}}$, ${\displaystyle {\begin{pmatrix}1&a\\0&0\\0&0\end{pmatrix}}}$, ${\displaystyle {\begin{pmatrix}0&1\\0&0\\0&0\end{pmatrix}}}$, ${\displaystyle {\begin{pmatrix}1&0\\0&1\\0&0\end{pmatrix}}}$
4. ${\displaystyle {\begin{pmatrix}0&0&0\\0&0&0\\0&0&0\end{pmatrix}}}$, ${\displaystyle {\begin{pmatrix}1&a&b\\0&0&0\\0&0&0\end{pmatrix}}}$, ${\displaystyle {\begin{pmatrix}0&1&a\\0&0&0\\0&0&0\end{pmatrix}}}$, ${\displaystyle {\begin{pmatrix}0&0&1\\0&0&0\\0&0&0\end{pmatrix}}}$, ${\displaystyle {\begin{pmatrix}1&0&a\\0&1&b\\0&0&0\end{pmatrix}}}$, ${\displaystyle {\begin{pmatrix}1&a&0\\0&0&1\\0&0&0\end{pmatrix}}}$, ${\displaystyle {\begin{pmatrix}0&1&0\\0&0&1\\0&0&0\end{pmatrix}}}$, ${\displaystyle {\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}}}$

Problem 6

What results from applying Gauss-Jordan reduction to a nonsingular matrix?

Answer

A nonsingular homogeneous linear system has a unique solution. So a nonsingular matrix must reduce to a (square) matrix that is all ${\displaystyle 0}$'s except for ${\displaystyle 1}$'s down the upper-left to lower-right diagonal, e.g.,

${\displaystyle {\begin{pmatrix}1&0\\0&1\\\end{pmatrix}},\quad {\text{or}}\quad {\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}},\quad {\text{etc.}}}$

Problem 7

The proof of Lemma 4 contains a reference to the ${\displaystyle i\neq j}$ condition on the row pivoting operation.

1. The definition of row operations has an ${\displaystyle i\neq j}$ condition on the swap operation ${\displaystyle \rho _{i}\leftrightarrow \rho _{j}}$. Show that in ${\displaystyle A{\xrightarrow[{}]{\rho _{i}\leftrightarrow \rho _{j}}}\;{\xrightarrow[{}]{\rho _{i}\leftrightarrow \rho _{j}}}A}$ this condition is not needed.
2. Write down a ${\displaystyle 2\!\times \!2}$ matrix with nonzero entries, and show that the ${\displaystyle -1\cdot \rho _{1}+\rho _{1}}$ operation is not reversed by ${\displaystyle 1\cdot \rho _{1}+\rho _{1}}$.
3. Expand the proof of that lemma to make explicit exactly where the ${\displaystyle i\neq j}$ condition on pivoting is used.

Answer

1. The ${\displaystyle \rho _{i}\leftrightarrow \rho _{i}}$ operation does not change ${\displaystyle A}$.
2. For instance,

   ${\displaystyle {\begin{pmatrix}1&2\\3&4\end{pmatrix}}{\xrightarrow[{}]{-\rho _{1}+\rho _{1}}}{\begin{pmatrix}0&0\\3&4\end{pmatrix}}{\xrightarrow[{}]{\rho _{1}+\rho _{1}}}{\begin{pmatrix}0&0\\3&4\end{pmatrix}}}$

   leaves the matrix changed.
3. If ${\displaystyle i\neq j}$ then

   ${\displaystyle {\begin{array}{rcl}{\begin{pmatrix}\vdots \\a_{i,1}&\cdots &a_{i,n}\\\vdots \\a_{j,1}&\cdots &a_{j,n}\\\vdots \end{pmatrix}}&{\xrightarrow[{}]{k\rho _{i}+\rho _{j}}}&{\begin{pmatrix}\vdots \\a_{i,1}&\cdots &a_{i,n}\\\vdots \\ka_{i,1}+a_{j,1}&\cdots &ka_{i,n}+a_{j,n}\\\vdots \end{pmatrix}}\\&{\xrightarrow[{}]{-k\rho _{i}+\rho _{j}}}&{\begin{pmatrix}\vdots \\a_{i,1}&\cdots &a_{i,n}\\\vdots \\-ka_{i,1}+ka_{i,1}+a_{j,1}&\cdots &-ka_{i,n}+ka_{i,n}+a_{j,n}\\\vdots \end{pmatrix}}\end{array}}}$

   does indeed give ${\displaystyle A}$ back. (Of course, if ${\displaystyle i=j}$ then the third matrix would have entries of the form ${\displaystyle -k(ka_{i,j}+a_{i,j})+ka_{i,j}+a_{i,j}}$.)