If you find any mistakes, please make a comment! Thank you.

## Solution to Linear Algebra Hoffman & Kunze Chapter 1.6

#### Exercise 1.6.1

As in Exercise 4, Section 1.5, we row reduce and keep track of the elementary matrices involved. It takes nine steps to put $A$ in row-reduced form resulting in the matrix
$$P=\left[\begin{array}{ccc}3/8&-1/4&3/8\\1/4&0&-1/4\\1/8&1/4&1/8\end{array}\right].$$

#### Exercise 1.6.2

Same story as Exercise 1, we get to the identity matrix in nine elementary steps. Multiplying those nine elementary matrices together gives
$$P=\rule{0mm}{5mm}\left[\begin{array}{ccc} 1/3& -\frac{29+3i}{30} & \frac{1-3i}{10} \\ 0\rule{0mm}{5mm} & -\frac{3+i}{10} & \frac{1-3i}{10} \\ -i/3\rule{0mm}{5mm} & \frac{3+i}{15} & \frac{3+i}{5} \end{array}\right].$$

#### Exercise 1.6.3

For the first matrix we row-reduce the augmented matrix as follows:
$$\left[\begin{array}{ccc|ccc} 2 & 5 & -1 & 1 & 0 & 0 \\ 4 & -1 & 2 & 0 & 1 & 0\\ 6 & 4 & 1 & 0 & 0 & 1\end{array}\right]$$$$\rightarrow \left[\begin{array}{ccc|ccc} 2 & 5 & -1 & 1 & 0 & 0 \\ 0 & -11 & 4 & -2 & 1 & 0\\ 0 & -11 & 4 & -3 & 0 & 1\end{array}\right]$$$$\rightarrow \left[\begin{array}{ccc|ccc} 2 & 5 & -1 & 1 & 0 & 0 \\ 0 & -11 & 4 & -2 & 1 & 0\\ 0 & 0 & 0 & -1 & -1 & 1\end{array}\right]$$At this point we see that the matrix is not invertible since we have obtained an entire row of zeros.

For the second matrix we row-reduce the augmented matrix as follows:
$$\left[\begin{array}{ccc|ccc} 1 & -1 & 2 & 1 & 0 & 0 \\ 3 & 2 & 4 & 0 & 1 & 0\\ 0 & 1 & -2 & 0 & 0 & 1\end{array}\right]$$$$\rightarrow\left[\begin{array}{ccc|ccc} 1 & -1 & 2 & 1 & 0 & 0 \\ 0 & 5 & -2 & -3 & 1 &0 \\ 0 & 1 & -2 & 0 & 0 & 1\end{array}\right]$$$$\rightarrow\left[\begin{array}{ccc|ccc} 1 & -1 & 2 & 1 & 0 & 0 \\ 0 & 1 & -2 & 0 & 0 & 1\\ 0 & 5 & -2 & -3 & 1 & 0\end{array}\right]$$$$\rightarrow\left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & -2 & 0 & 0 & 1\\ 0 & 0 & 8 & -3 & 1 & -5\end{array}\right]$$$$\rightarrow\left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & -2 & 0 & 0 & 1\\ 0 & 0 & 1 & -3/8 & 1/8 & -5/8\end{array}\right]$$$$\rightarrow\left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & -3/4 & 1/4 & -1/4\\ 0 & 0 & 1 & -3/8 & 1/8 & -5/8\end{array}\right]$$Thus the inverse matrix is
$$\left[\begin{array}{ccc} 1 & 0 & 1 \\ -3/4 & 1/4 & -1/4\\ 3/8 & 1/8 & -5/8\end{array}\right].$$

#### Exercise 1.6.4

Note that$$\left[\begin{array}{ccc}5&0&0\\1&5&0\\0&1&5\end{array}\right]\left[\begin{array}{c}x\\y\\z\end{array}\right]=c\left[\begin{array}{c}x\\y\\z\end{array}\right]$$
implies
\begin{alignat}{1}\label{a1}
5x &= cx\\ \label{a2}
x+5y &= cy\\\label{a3}
y+5z &= cz
\end{alignat}Now if $c\not=5$ then (\ref{a1}) implies $x=0$, and then (\ref{a2}) implies $y=0$, and then (\ref{a3}) implies $z=0$. So it is true for $\left[\begin{array}{c}0\\0\\0\end{array}\right]$ with $c=0$.

If $c=5$ then (\ref{a2}) implies $x=0$ and (\ref{a3}) implies $y=0$. So if $c=5$ any such vector must be of the form $\left[\begin{array}{c}0\\0\\z\end{array}\right]$ and indeed any such vector works with $c=5$.

So the final answer is any vector of the form $\left[\begin{array}{c}0\\0\\z\end{array}\right]$.

#### Exercise 1.6.5

We row-reduce the augmented matrix as follows:
$$\left[\begin{array}{cccc|cccc} 1 & 2 & 3 & 4 & 1 & 0 & 0 & 0 \\ 0 & 2 & 3 & 4 & 0 & 1 & 0 & 0 \\ 0 & 0 & 3 & 4 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 4 & 0 & 0 & 0 & 1 \end{array}\right]$$$$\rightarrow\left[\begin{array}{cccc|cccc} 1 & 0 & 0 & 0 & 1 & -1 & 0 & 0 \\ 0 & 2 & 3 & 4 & 0 & 1 & 0 & 0 \\ 0 & 0 & 3 & 4 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 4 & 0 & 0 & 0 & 1 \end{array}\right]$$$$\rightarrow\left[\begin{array}{cccc|cccc} 1 & 0 & 0 & 0 & 1 & -1 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 & 1 & -1 & 0 \\ 0 & 0 & 3 & 4 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 4 & 0 & 0 & 0 & 1 \end{array}\right]$$$$\rightarrow\left[\begin{array}{cccc|cccc} 1 & 0 & 0 & 0 & 1 & -1 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 & 1 & -1 & 0 \\ 0 & 0 & 3 & 0 & 0 & 0 & 1 & -1 \\ 0 & 0 & 0 & 4 & 0 & 0 & 0 & 1 \end{array}\right]$$$$\rightarrow\left[\begin{array}{cccc|cccc} 1 & 0 & 0 & 0 & 1 & -1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1/2 & -1/2 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1/3 & -1/3 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1/4 \end{array}\right]$$Thus the $A$ does have an inverse and
$$A^{-1}=\left[\begin{array}{cccc} 1 & -1 & 0 & 0 \\ 0 & 1/2 & -1/2 & 0 \\ 0 & 0 & 1/3 & -1/3 \\ 0 & 0 & 0 & 1/4 \end{array}\right].$$

#### Exercise 1.6.6

Write $A=\left[\begin{array}{c}a_1\\a_2\end{array}\right]$ and $B=[b_1\ \ b_2]$. Then
$$AB=\left[\begin{array}{cc} a_1b_1 & a_1b_2\\ a_2b_1 & a_2b_2\end{array}\right].$$If any of $a_1,a_2,b_1$ or $b_2$ equals zero then $AB$ has an entire row or an entire column of zeros. A matrix with an entire row or column of zeros is not invertible. Thus assume $a_1,a_2,b_1$ and $b_2$ are non-zero. Now if we add $-a_2/a_1$ of the first row to the second row we get
$$\left[\begin{array}{cc} a_1b_1 & a_1b_2\\ 0 & 0\end{array}\right].$$Thus $AB$ is not row-equivalent to the identity. Thus by Theorem 12 page 23, $AB$ is not invertible.

#### Exercise 1.6.7

(a) $0=A^{-1}0=A^{-1}(AB)=(A^{-1}A)B=IB=B$. Thus $B=0$.

(b) By Theorem 13 (ii) since $A$ is not invertible $AX=0$ must have a non-trivial solution $v$. Let $B$ be the matrix all of whose columns are equal to $v$. Then $B\not=0$ but $AB=0$.

#### Exercise 1.6.8

Suppose
$$A=\left[\begin{array}{cc}a&b\\c&d\end{array}\right],\quad B=\left[\begin{array}{cc}x & y\\z & w\end{array}\right].$$Then
$$AB=\left[\begin{array}{cc}ax+bz & ay+bw\\cx+dz & cy+dw\end{array}\right].$$Then $AB=I$ implies the following system in $u,r,s,t$ has a solution
\begin{alignat*}{1}
au+bs &= 1\\
cu+ds &= 0\\
ar+bt &= 0\\
cr + dt &= 1
\end{alignat*}because $(x,y,z,w)$ is one such solution. The augmented coefficient matrix of this system is

\left[\begin{array}{cccc|c}
a & 0 & b & 0 & 1\\
c & 0 & d & 0 & 0\\
0 & a & 0 & b & 0\\
0 & c & 0 & d & 1
\end{array}\right].
\label{mz1}
As long as $ad-bc\not=0$ this system row-reduces to the following row-reduced echelon form
$$\left[\begin{array}{cccc|c} 1 & 0 &0 & 0 & d/(ad-bc)\\ 0 & 1 & 0 & 0 & -b/(ad-bc)\\ 0 & 0 & 1 & 0 & -c/(ad-bc)\\ 0 & 0 & 0 & 1 & a/(ad-bc) \end{array}\right]$$Thus we see that $x=d/(ad-bc)$, $y=-b/(ad-bc)$, $z=-c/(ad-bc)$, $w=a/(ad-bc)$ and
$$A^{-1}=\left[\begin{array}{cc} d/(ad-bc) & -b/(ad-bc)\\ -c/(ad-bc) & a/(ad-bc) \end{array}\right].$$Now it’s a simple matter to check that
$$\left[\begin{array}{cc} d/(ad-bc) & -b/(ad-bc)\\ -c/(ad-bc) & a/(ad-bc) \end{array}\right] \cdot \left[\begin{array}{cc}a & b\\c & d\end{array}\right] = \left[\begin{array}{cc}1 & 0\\ 0 & 1\end{array}\right].$$Now suppose that $ad-bc=0$. We will show there is no solution. If $a=b=c=d=0$ then obviously $A$ has no inverse. So suppose WOLOG that $a\not=0$ (because by elementary row and column operations we can move any of the four elements to be the top left entry, and elementary row and column operations do not change a matrix’s status as being invertible or not). Subtracting $\frac ca$ times the 3rd row from the 4th row of (\ref{mz1}) gives
$$\left[\begin{array}{cccc|c} a & 0 & b & 0 & 1\\ c & 0 & d & 0 & 0\\ 0 & a & 0 & b & 0\\ 0 & c-\frac caa & 0 & d-\frac cab & 1 \end{array}\right].$$Now $c-\frac caa=0$ and since $ad-bc=0$ also $d-\frac cab=0$. Thus we get
$$\left[\begin{array}{cccc|c} a & 0 & b & 0 & 1\\ c & 0 & d & 0 & 0\\ 0 & a & 0 & b & 0\\ 0 & 0 & 0 & 0 & 1 \end{array}\right].$$and it follows that $A$ is not invertible.

#### Exercise 1.6.9

Suppose that $a_{ii}\not=0$ for all $i$. Then we can divide row $i$ by $a_{ii}$ to give a row-equivalent matrix which has all ones on the diagonal. Then by a sequence of elementary row operations we can turn all off diagonal elements into zeros. We can therefore row-reduce the matrix to be equivalent to the identity matrix. By Theorem 12 page 23, $A$ is invertible.

Now suppose that some $a_{ii}=0$. If all $a_{ii}$’s are zero then the last row of the matrix is all zeros. A matrix with a row of zeros cannot be row-equivalent to the identity so cannot be invertible. Thus we can assume there’s at least one $i$ such that $a_{ii}\not=0$. Let $i’$ be the largest such index, so that $a_{i’i’}=0$ and $a_{ii}\not=0$ for all $i>i’$. We can divide all rows with $i>i’$ by $a_{ii}$ to give ones on the diagonal for those rows. We can then add multiples of those rows to row $i’$ to turn row $i’$ into an entire row of zeros. Since again $A$ is row-equivalent to a matrix with an entire row of zeros, it cannot be invertible.

#### Exercise 1.6.10

There are $n$ colunms in $A$ so the vector space generated by those columns has dimension no greater than $n$. All columns of $AB$ are linear combinations of the columns of $A$. Thus the vector space generated by the columns of $AB$ is contained in the vector space generated by the columns of $A$. Thus the column space of $AB$ has dimension no greater than $n$. Thus the column space of the $m\times m$ matrix $AB$ has dimension less or equal to $n$ and $n<m$. Thus the columns of $AB$ generate a space of dimension strictly less than $m$. Thus $AB$ is not invertible.

#### Exercise 1.6.11

First put $A$ in row-reduced echelon form, $R’$. So $\exists$ an invertible $m\times m$ matrix $P$ such that $R’=PA$. Each row of $R’$ is either all zeros or starts (on the left) with zeros, then has a one, then may have non-zero entries after the one. Suppose row $i$ has a leading one in the $j$-th column. The $j$-th column has zeros in all other places except the $i$-th, so if we add a multiple of this column to another column then it only affects entries in the $i$-th row. Therefore a sequence of such operations can turn this row into a row of all zeros and a single one.

Let $B$ be the $n\times n$ matrix such that $B_{rr}=1$ and $B_{rs}=0$ $\forall$ $r\not=s$ except $B_{jk}\not=0$. Then $AB$ equals $A$ with $B_{jk}$ times column $j$ added to column $k$. $B$ is invertible since any such operation can be undone by another such operation. By a sequence of such operations we can turn all values after the leading one into zeros. Let $Q$ be a product of all of the elementary matrices $B$ involved in this transformation. Then $PAQ$ is in row-reduced and column-reduced form.

Exercise 1.6.12

This problem seems a bit hard for this book. There are a class of theorems like this, in particular these are called Hilbert Matrices and a proof is given in this article on arxiv by Christian Berg called Fibonacci numbers and orthogonal polynomials. See Theorem 4.1. Also there might be a more elementary proof in this discussion on mathoverflow.net where several proofs are given: Deriving inverse of Hilbert matrix. Also see http://vigo.ime.unicamp.br/HilbertMatrix.pdf where a general formula for the $i,j$ entry of the inverse is given explicitly as
$$(-1)^{i+j}(i+j-1){{n+i-1}\choose{n-j}}{n+j-1\choose n-i}{i+j-1\choose i-1}^2$$