Solution Manual of "Elementary Linear Algebra": 2. Matrices (Part-2)

This document is the solution manual of “Elementary Linear Algebra” which was written by K. R. Matthews, University of Queensland.
The free printable PDF format lecture can be Downloaded Here

Summary

• Non-singular matrix
  A matrix $A\in M_{n\times n}(F)$ is called non-singular or invertible if there exists a matrix $B\in M_{n\times n}(F)$ such that $$AB=I_n=BA.$$ Any matrix $B$ with the above property is called an inverse of $A$. If $A$ does not have an inverse, $A$ is called singular.
• Inverses are unique
  If $A$ has inverse $B$ and $C$, then $B=C$.
  (Since $B=BI_n=B(AC)=(BA)C=I_nC=C$)
• If $A$ and $B$ are non-singular matrices of the same size, then so is $AB$. Moreover $$(AB)^{-1}=B^{-1}A^{-1}.$$
  (Since $(AB)(B^{-1}A^{-1})=ABB^{-1}A^{-1}=AI_nA^{-1}=I_n$)
  The above result generalizes to a product of $m$ non-singular matrices: If $A_1,\cdots, A_m$ are non-singular $n\times n$ matrices, then the product $A_1\cdots A_n$ is also non-singular. Moreover $$(A_1\cdots A_m)^{-1}=A_m^{-1}\cdots A_{1}^{-1}.$$
• Let $A=\begin{bmatrix}a& b \\ c&d \end{bmatrix}$ and $\Delta=ad-bc\neq0$. Then $A$ is non-singular. Also $$A^{-1}=\Delta^{-1}\begin{bmatrix}d & -b\\ -c &a \end{bmatrix}$$
• If the coefficient matrix $A$ of a system of $n$ equations in $n$ unknown is non-singular, then the system $AX=B$ has the unique solution $X=A^{-1}B$.
• Cramer's rule for 2 equations in 2 unknowns
  The system $$\begin{cases}ax+by=e \\ cx+dy=f \end{cases}$$ has a unique solution if $\Delta=\begin{vmatrix}a & b\\ c&d \end{vmatrix} \neq0$, namely $$x={\Delta_1\over\Delta},\ y={\Delta_2\over\Delta}$$ where $$\Delta_1=\begin{vmatrix}e & b \\ f & d \end{vmatrix},\ \Delta_2=\begin{vmatrix}a & e \\ c & f \end{vmatrix}.$$ Based on the above theorem, we have the following corollary:
  The homogeneous system $$\begin{cases}ax+by=0 \\ cx+dy=0 \end{cases}$$ has only the trivial solution (i.e. zero) if $\Delta=\begin{vmatrix}a & b\\ c & d \end{vmatrix}\neq0.$
• Let $A$ be a square matrix. If $A$ is non-singular, the homogeneous system $AX=0$ has only the trivial solution. Equivalently, if the homogeneous system $AX=0$ has a non-trivial solution, then $A$ is singular.
  (Since if $A$ is non-singular then it has inverse matrix and hence $AX=0\Rightarrow X=A^{-1}0=0$)
• Elementary row matrices
  To each of the three types of elementary row operation, there corresponds an elementary row matrix, denoted by $E_{ij},\ E_{i}(t),\ E_{ij}(t)$:
  
  • $E_{ij}, (i\neq j)$ is obtained from the identity matrix $I_n$ by interchanging rows $i$ and $j$.
  • $E_{i}(t)$ is obtained by multiplying the $i-$th row of $I_n$ by $t$.
  • $E_{ij}(t),\ (i\neq j)$ is obtained from $I_n$ by adding $t$ times the $j-$th row of $I_n$ to the $i-$th row.
• If a matrix $A$ is pre-multiplied by an elementary row matrix, the resulting matrix is the one obtained b performing the corresponding elementary row-operation on $A$.
• Elementary row-matrices are non-singular. Indeed,
  
  • $E_{ij}^{-1}=E_{ij}$
  • $E_{i}^{-1}(t)=E_{i}(t^{-1})$
  • $E_{ij}^{-1}(t)=E_{ij}(-t)$
• Let $A$ be non-singular $n\times n$ matrix. Then
  
  • $A$ is row-equivalent to $I_n$,
  • $A$ is a product of elementary row matrices.
• Let $A$ be $n\times n$ and suppose that $A$ is row-equivalent to $I_n$. Then $A$ is non-singular and $A^{-1}$ can be found by performing the same sequence of elementary row operation on $I_n$ as were used to convert $A$ to $I_n$.
  (Since $I_n=E_r\cdots E_1A=BA\Rightarrow A^{-1}=B=(E_r\cdots E_1)I_n$, which means $A^{-1}$ is obtained from $I_n$ by performing the same sequence of elementary row operations as were used to convert $A$ to $I_n$.)
  An important corollary is that if $A$ is singular, then $A$ is row-equivalent to a matrix whose last row is zero.
• The transpose of a matrix
  Let $A$ be an $m\times n$ matrix. Then $A^{t}$, the transpose of $A$, is the matrix obtained by interchanging the rows and columns of $A$. In other words if $A=[a_{ij}]$, then $(A^{t})_{ji}=a_{ij}$. Consequently $A^{t}$ is $n\times m$.
  
  • $(A^{t})^{t}=A$;
  • $(A\pm B)^{t}=A^{t}\pm B^{t}$ if $A$ and $B$ are $m\times n$;
  • $(sA)^{t}=sA^{t}$ if $s$ is a scalar;
  • $(AB)^{t}=B^{t}A^{t}$ if $A$ is $m\times n$ and $B$ is $n\times p$;
    (Suppose $A=[a_{ij}],\ B=[b_{jk}]$, we have $((AB)^{t})_{ki}=(AB)_{ik}=\displaystyle\sum_{j=1}^{n}a_{ij}b_{jk} = \sum_{j=1}^{n}(B^{t})_{kj}(A^{t})_{ji}=(B^{t}A^{t})_{ki}$)
  • If $A$ is non-singular, then $A^{t}$ is also non-singular and $$(A^{t})^{-1}(A^{-1})^{t};$$
  • $X^{t}X=x_1^2+\cdots+x_n^2$ if $X=[x_1,\cdots,x_n]^{t}$ is a column vector.
• Symmetric matrix
  A matrix $A$ is symmetric if $A^{t}=A$. In other words $A$ is square (say $n\times n$) and $a_{ji}=a_{ij}$ for all $1\leq i \leq n,\ 1 \leq j \leq n$. Hence $$A=\begin{bmatrix}a&b\\b&c \end{bmatrix}$$ is a general $2\times2$ symmetric matrix.
• Skew-symmetric matrix
  A matrix $A$ is called skew-symmetric if $A^{t}=-A$. In other words $A$ is square (say $n\times n$) and $a_{ji}=-a_{ij}$ for all $1\leq i \leq n,\ 1 \leq j \leq n$ (note that $a_{ii}=0$). Hence $$A=\begin{bmatrix}0&b\\-b&0 \end{bmatrix}$$ is a general $2\times2$ skew-symmetric matrix.
• Normal equations
  Suppose $AX=B$ represents a system of linear equations with real coefficients. The associated system $A^{t}AX=A^{t}B$ is always consistent and that the any solution of this system minimize the sum $r_1^2+\cdots+r_m^2$, where $r_1,\cdots,r_m$ (the residuals) are defined by $$r_i=a_{i1}x_1+\cdots+a_{in}x_n-b_i$$ for $i=1,\cdots, m$. The equations represented by $A^{t}AX=A^{t}B$ are called normal equations corresponding to the system $AX=B$ and any solution of the system of normal equations is called a least squares solution of the original system. More details can be found at HERE.

Problems 2.7

1. Let $A=\begin{bmatrix}1 & 4\\ -3 &1 \end{bmatrix}$. Prove that $A$ is non-singular, find $A^{-1}$ and express $A$ as a product of elementary row matrices.

Solution:
$$\begin{bmatrix}1& 4& 1& 0\\ -3 &1 &0& 1 \end{bmatrix}\Rightarrow R_2+3R_1 \begin{bmatrix}1& 4& 1& 0\\ 0 &13 &3& 1 \end{bmatrix}$$ $$\Rightarrow {1\over13}R_2 \begin{bmatrix}1& 4& 1& 0\\ 0 &1 &{3\over13}& {1\over13} \end{bmatrix} \Rightarrow R_1-4R_2 \begin{bmatrix}1& 0& {1\over13}& -{4\over13}\\ 0 &1 &{3\over13}& {1\over13} \end{bmatrix}$$ Thus $A$ is non-singular and $A^{-1}= \begin{bmatrix}{1\over13}& -{4\over13}\\ {3\over13}& {1\over13} \end{bmatrix}$.
Next, we have $$I_2=E_{12}(-4)E_{2}({1\over13})E_{21}(3)A$$ $$\Rightarrow A^{-1}=E_{12}(-4)E_{2}({1\over13})E_{21}(3)$$ $$\Rightarrow A=(A^{-1})^{-1}=(E_{12}(-4)E_{2}({1\over13})E_{21}(3))^{-1}$$ $$=E_{21}(3)^{-1}E_{2}({1\over13})^{-1}E_{12}(-4)^{-1} = E_{21}(-3)E_{2}(13)E_{12}(4)$$
2. A square matrix $D=[d_{ij}]$ is called diagonal if $d_{ij}=0$ for $i\neq j$. (That is the off-diagonal elements are zero.) Prove that pre-multiplication of a matrix $A$ by a diagonal matrix $D$ results in matrix $DA$ whose rows are the rows of $A$ multiplied by the respective diagonal elements of $D$. State and prove a similar result for post-multiplication by a diagonal matrix.
Let $\text{diag}(a_1,\cdots,a_n)$ denote the diagonal matrix whose diagonal elements $d_{ii}$ are $a_1, \cdots, a_n$, respectively. Show that $$\text{diag}(a_1,\cdots,a_n)\text{diag}(b_1,\cdots,b_n)=\text{diag}(a_1b_1,\cdots,a_nb_n)$$ and deduce that if $a_1\cdots a_n\neq0$, then $\text{diag}(a_1,\cdots,a_n)$ is non-singular and $$(\text{diag}(a_1,\cdots,a_n))^{-1}=\text{diag}(a_1^{-1},\cdots,a_n^{-1}).$$ Also prove that $\text{diag}(a_1,\cdots,a_n)$ is singular if $a_i=0$ for some $i$.

Solution:
Let $D=[d_{ij}]$ be an $m\times m$ diagonal matrix and let $A=[a_{jk}]$ be an $m\times n$ matrix. Thus $$(DA)_{ik}=\sum_{j=1}^{m}d_{ij}a_{jk} = d_{ii}a_{ik}$$ for $i=1,\cdots,m$ as $d_{ij}=0$ while $i\neq j$. It follows that the $i-$th row of $DA$ is obtained by multiplying the $i$th row of $A$ by $d_{ii}$.
Similarly, post-multiplication of a matrix $A$ by a diagonal matrix $D$ results in a matrix whose columns are those of $A$, multiplied by the respective diagonal elements of $D$.
Next, $$\text{diag}(a_1,\cdots,a_n)\text{diag}(b_1,\cdots,b_n) = \text{diag}(a_1b_1,\cdots,a_nb_n)$$ can be seen as the pre-multiplication of the matrix $\text{diag}(b_1,\cdots,b_n)$ by the diagonal matrix $\text{diag}(a_1,\cdots,a_n)$.
Finally, if $a_i\neq0$ for $i=1,\cdots,n$, then $a_i^{-1}$ exists and hence $$\text{diag}(a_1,\cdots,a_n)\text{diag}(a_1^{-1},\cdots,a_n^{-1})=\text{diag}(1,\cdots,1)=I_n$$ which means $\text{diag}(a_1,\cdots,a_n)$ is non-singular and its inverse is $\text{diag}(a_1^{-1},\cdots,a_n^{-1})$.


3. Let $A=\begin{bmatrix}0& 0& 2\\1& 2& 6\\ 3&7&9 \end{bmatrix}$. Prove that $A$ is non-singular, find $A^{-1}$ and express $A$ as a product of elementary row matrices.

Solution:
$$\begin{bmatrix}0& 0& 2& 1 & 0 & 0\\ 1& 2&6 & 0 & 1 & 0\\ 3& 7& 9 & 0& 0& 1 \end{bmatrix}$$ $$\Rightarrow R_1\leftrightarrow R_2 \begin{bmatrix} 1& 2&6 & 0 & 1 & 0\\ 0& 0& 2& 1 & 0 & 0\\3& 7& 9 & 0& 0& 1 \end{bmatrix}$$ $$\Rightarrow R_3-3R_1 \begin{bmatrix} 1& 2&6 & 0 & 1 & 0\\ 0& 0& 2& 1 & 0 & 0\\0& 1&- 9 & 0& -3& 1 \end{bmatrix}$$ $$\Rightarrow R_2\leftrightarrow R_3 \begin{bmatrix} 1& 2&6 & 0 & 1 & 0\\ 0& 1&- 9 & 0& -3& 1\\0& 0& 2& 1 & 0 & 0 \end{bmatrix}$$ $$\Rightarrow {1\over2}R_3 \begin{bmatrix} 1& 2&6 & 0 & 1 & 0\\ 0& 1&- 9 & 0& -3& 1\\0& 0& 1& {1\over2} & 0 & 0 \end{bmatrix}$$ $$\Rightarrow \begin{cases}R_1-2R_2\\ R_2+9R_3 \end{cases} \begin{bmatrix} 1& 0&24 & 0 & 7 & -2\\ 0& 1&0 & {9\over2}& -3& 1\\0& 0& 1& {1\over2} & 0 & 0 \end{bmatrix}$$ $$\Rightarrow R_1-24R_3 \begin{bmatrix} 1& 0&0& -12 & 7 & -2\\ 0& 1&0 & {9\over2}& -3& 1\\0& 0& 1& {1\over2} & 0 & 0 \end{bmatrix}$$ Thus $A$ is non-singular and $A^{-1}= \begin{bmatrix} -12 & 7 & -2\\ {9\over2}& -3& 1\\{1\over2} & 0 & 0 \end{bmatrix}$.
Next, since we have $$I_3=E_{13}(-24)E_{23}(9)E_{12}(-2)E_{3}({1\over2})E_{23}E_{31}(-3)E_{12}A$$ $$\Rightarrow A^{-1}= E_{13}(-24)E_{23}(9)E_{12}(-2)E_{3}({1\over2})E_{23}E_{31}(-3)E_{12}$$ Thus $$A=(A^{-1})^{-1}=(E_{13}(-24)E_{23}(9)E_{12}(-2)E_{3}({1\over2})E_{23}E_{31}(-3)E_{12})^{-1}$$ $$=E_{12}E_{31}(3)E_{23}E_{3}(2)E_{12}(2)E_{23}(-9)E_{13}(24)$$
4. Find the rational number $k$ for which the matrix $A=\begin{bmatrix}1& 2& k\\ 3& -1& 1\\ 5& 3& -5 \end{bmatrix}$ is singular.

Solution:
$$A=\begin{bmatrix}1& 2& k\\ 3& -1& 1\\ 5& 3& -5 \end{bmatrix}$$ $$\Rightarrow \begin{cases}R_2-3R_1\\ R_3-5R_1\end{cases}\begin{bmatrix}1& 2& k\\ 0& -7& 1-3k\\ 0& -7& -5-5k \end{bmatrix}$$ $$\Rightarrow R_3-R_2\begin{bmatrix}1& 2& k\\ 0& -7& 1-3k\\ 0& 0& -6-2k \end{bmatrix}$$ Thus $A$ is singular if $-6-2k=0\Rightarrow k=-3$.


5. Prove that $A=\begin{bmatrix}1& 2\\ -2& -4 \end{bmatrix}$ is singular and find a non-singular matrix $P$ such that $PA$ has last row zero.

Solution:
$$A=\begin{bmatrix}1& 2\\ -2& -4 \end{bmatrix}$$ $$\Rightarrow R_2+2R_1 \begin{bmatrix}1& 2\\ 0& 0 \end{bmatrix}$$ That is, $A$ is singular and $P=E_{21}(2)=\begin{bmatrix}1& 0\\ 2& 1 \end{bmatrix}$.


6. If $A=\begin{bmatrix}1& 4\\-3& 1 \end{bmatrix}$, verify that $A^2-2A+13I_2=0$ and deduce that $A^{-1}=-{1\over13}(A-2I_2)$.

Solution:
$$A=\begin{bmatrix}1& 4\\-3& 1 \end{bmatrix}\Rightarrow A^2=AA=\begin{bmatrix}1& 4\\-3& 1 \end{bmatrix}\cdot\begin{bmatrix}1& 4\\-3& 1 \end{bmatrix} =\begin{bmatrix}-11& 8\\-6& -11 \end{bmatrix}$$ $$\Rightarrow A^2-2A+13I_2= \begin{bmatrix}-11& 8\\-6& -11 \end{bmatrix} - \begin{bmatrix}2& 8\\-6& 2 \end{bmatrix} + \begin{bmatrix}13& 0\\0& 13 \end{bmatrix} = 0$$ Since $A^2-2A+13I_2=0$, we have $$A(A-2I_2)=-13I_2=(A-2I_2)A \Rightarrow A^{-1}=-{1\over13}(A-2I_2)$$
7. Let $A = \begin{bmatrix}1& 1& -1\\0& 0& 1\\ 2& 1& 2 \end{bmatrix}$.
(1) Verify that $A^3=3A^2-3A+I_3$.
(2) Express $A^4$ in terms of $A^2$, $A$ and $I_3$ and hence calculate $A^4$ explicitly.
(3) Use (1) to prove that $A$ is non-singular and find $A^{-1}$ explicitly.

Solution:
(1) $$A = \begin{bmatrix}1& 1& -1\\0& 0& 1\\ 2& 1& 2 \end{bmatrix} \Rightarrow A^2=AA=\begin{bmatrix}1& 1& -1\\0& 0& 1\\ 2& 1& 2 \end{bmatrix}\cdot\begin{bmatrix}1& 1& -1\\0& 0& 1\\ 2& 1& 2 \end{bmatrix} = \begin{bmatrix}-1& 0& -2\\2& 1& 2\\ 6& 4& 3 \end{bmatrix}$$ $$\Rightarrow A^3=A^2A = \begin{bmatrix}-1& 0& -2\\2& 1& 2\\ 6& 4& 3 \end{bmatrix}\cdot \begin{bmatrix}1& 1& -1\\0& 0& 1\\ 2& 1& 2 \end{bmatrix} = \begin{bmatrix}-5& -3& -3\\6& 4& 3\\ 12& 9& 4 \end{bmatrix}$$ Thus $$3A^2-3A+I_3= \begin{bmatrix}-3& 0& -6\\6& 3& 6\\ 18& 12& 9 \end{bmatrix} - \begin{bmatrix}3& 3& -3\\0& 0& 3\\ 6& 3& 6 \end{bmatrix} + \begin{bmatrix}1& 0& 0\\0& 1& 0\\ 0& 0& 1 \end{bmatrix}$$ $$=\begin{bmatrix}-5& -3& -3\\6& 4& 3\\ 12& 9& 4 \end{bmatrix} = A^3$$
(2) $$A^4=A^3A=(3A^2-3A+I_3)A = 3A^3-3A^2+A$$ $$= 3(3A^2-3A+I_3) -3A^2 + A = 6A^2-8A+3I_3$$ $$=\begin{bmatrix}-6& 0& -12\\12& 6& 12\\ 36& 24& 18 \end{bmatrix} - \begin{bmatrix}8& 8& -8\\0& 0& 8\\ 16& 8& 16 \end{bmatrix} + \begin{bmatrix}3& 0& 0\\0& 3& 0\\ 0& 0& 3 \end{bmatrix}$$ $$= \begin{bmatrix}-11& -8& -4\\12& 9& 4\\ 20& 16& 5 \end{bmatrix}$$
(3) Since $A^3=3A^2-3A+I_3$, we have $$A^3-3A^2+3A=I_3$$ $$\Rightarrow A(A^2-3A+3I_3) = I_3 = (A^2-3A+3I_3)A$$ Thus $A$ is non-singular and $$A^{-1}= A^2-3A+3I_3 = \begin{bmatrix}-1& 0& -2\\2& 1& 2\\ 6& 4& 3 \end{bmatrix} - \begin{bmatrix}3& 3& -3\\0& 0& 3\\ 6& 3& 6 \end{bmatrix} + \begin{bmatrix}3& 0& 0\\0& 3& 0\\ 0& 0& 3 \end{bmatrix}$$ $$= \begin{bmatrix}-1& -3& 1\\2& 4& -1\\ 0& 1& 0 \end{bmatrix}$$
8. (1) Let $B$ be an $n\times n$ matrix such that $B^3=0$. If $A=I_n-B$, prove that $A$ is non-singular and $A^{-1}=I_n+B+B^2$.
Show that the system of linear equations $AX=b$ has the solution $$X=b+Bb+B^2b.$$
(2) If $B=\begin{bmatrix}0& r& s\\0& 0& t\\0& 0& 0 \end{bmatrix}$, verify that $B^3=0$ and use (1) to determine $(I_3-B)^{-1}$ explicitly.

Solution:
(1) Since $$AA^{-1}=(I_n-B)(I_n+B+B^2) = (I_n+B+B^2)-(B+B^2+B^3) = I_n$$ $$A^{-1}A=(I_n+B+B^2)(I_n-B)=(I_n-B)+(B-B^2)+(B^2-B^3) = I_n$$ Hence $A$ is non-singular and $A^{-1}=I_n+B+B^2$. And thus $$AX=b\Rightarrow A^{-1}AX=A^{-1}b\Rightarrow X= (I_n+B+B^2) b= b+Bb+B^2b$$
(2) $$B= \begin{bmatrix}0& r& s\\0& 0& t\\0& 0& 0 \end{bmatrix}$$ $$\Rightarrow B^2=BB= \begin{bmatrix}0& r& s\\0& 0& t\\0& 0& 0 \end{bmatrix} \cdot \begin{bmatrix}0& r& s\\0& 0& t\\0& 0& 0 \end{bmatrix} = \begin{bmatrix}0& 0& rt\\0& 0& 0\\0& 0& 0 \end{bmatrix}$$ $$\Rightarrow B^3=B^2B= \begin{bmatrix}0& 0& rt\\0& 0& 0\\0& 0& 0 \end{bmatrix}\cdot \begin{bmatrix}0& r& s\\0& 0& t\\0& 0& 0 \end{bmatrix} = 0$$ By the above result, we have $$(I_3-B)^{-1} = I_3+B+B^2$$ $$= \begin{bmatrix}1& 0& 0\\0& 1& 0\\ 0& 0& 1 \end{bmatrix} + \begin{bmatrix}0& r& s\\0& 0& t\\0& 0& 0 \end{bmatrix} + \begin{bmatrix}0& 0& rt\\0& 0& 0\\0& 0& 0 \end{bmatrix}$$ $$=\begin{bmatrix}1& r& s+rt\\0& 1& t\\0& 0& 1 \end{bmatrix}$$
9. Let $A$ be $n\times n$.
(1) If $A^2=0$, prove that $A$ is singular.
(2) If $A^2 = A$ and $A \neq I_n$, prove that $A$ is singular.

Solution:
(1) Suppose $A$ is non-singular, then $$A^{-1}A^2=A^{-1}0\Rightarrow A^{-1}AA=0 \Rightarrow A=0$$ whcih is contradiction since zero matrix is singular.
(2) Suppose $A$ is non-singular, then $$A^{-1}A^2 = A^{-1}A\Rightarrow A^{-1}AA=I_n \Rightarrow A=I_n$$ which means if $A^2 = A$ and $A \neq I_n$, then $A$ is singular.


10. Use Question 7 to solve the system of equations $$\begin{cases}x+y-z=a\\ z=b\\2x+y+2z=c \end{cases}$$ where $a$, $b$, $c$ are given rationals. Check your answer using the Gauss-Jordan algorithm.

Solution:
Rewrite the system as $AX=B$: $$\begin{bmatrix}1& 1& -1\\ 0& 0& 1\\ 2& 1& 2 \end{bmatrix}\cdot \begin{bmatrix}x\\y\\z \end{bmatrix} = \begin{bmatrix}a\\b\\c \end{bmatrix}$$ where $A= \begin{bmatrix}1& 1& -1\\ 0& 0& 1\\ 2& 1& 2 \end{bmatrix}$ satisfies $A^3=3A^2-3A+I_3$, and hence $A^{-1}=A^2-3A+3I_3$ according to Question 7. Thus $$X=A^{-1}B = (A^2-3A+3I_3)B$$ $$=\begin{bmatrix}-1& -3& 1\\2& 4& -1\\ 0& 1& 0 \end{bmatrix}\cdot \begin{bmatrix}a\\b\\c \end{bmatrix}=\begin{bmatrix}-a-3b+c\\2a+4b-c\\b \end{bmatrix}$$ That is, the solution is $$\begin{cases}x=a-3b+c\\y=2a+4b-c\\z=b\end{cases}$$
11. Determine explicitly the following products of $3\times3$ elementary row matrices.
(1) $E_{12}E_{23}$; (2) $E_{1}(5)E_{12}$; (3) $E_{12}(3)E_{21}(-3)$; (4) $(E_{1}(100))^{-1}$; (5) $E_{12}^{-1}$; (6) $(E_{12}(7))^{-1}$; (7) $(E_{12}(7)E_{31}(1))^{-1}$

Solution:
(1) $$E_{12}E_{23} = E_{12}\begin{bmatrix}1& 0& 0\\ 0& 0& 1\\ 0& 1& 0 \end{bmatrix} = \begin{bmatrix}0& 0& 1\\ 1& 0& 0\\ 0& 1& 0 \end{bmatrix}$$
(2) $$E_{1}(5)E_{12}= E_{1}(5) \begin{bmatrix}0& 1& 0\\ 1& 0& 0\\ 0& 0& 1 \end{bmatrix} = \begin{bmatrix}0& 5& 0\\ 1& 0& 0\\ 0& 0& 1 \end{bmatrix}$$
(3) $$E_{12}(3)E_{21}(-3) = E_{12}(3) \begin{bmatrix}1& 0& 0\\ -3& 1& 0\\ 0& 0& 1 \end{bmatrix} = \begin{bmatrix}-8& 3& 0\\ -3& 1& 0\\ 0& 0& 1 \end{bmatrix}$$
(4) $$(E_{1}(100))^{-1} =E_{1}({1\over100})= \begin{bmatrix}{1\over100}& 0& 0\\ 0& 1& 0\\ 0& 0& 1 \end{bmatrix}$$
(5) $$E_{12}^{-1} = E_{12} = \begin{bmatrix}0& 1& 0\\ 1& 0& 0\\ 0& 0& 1 \end{bmatrix}$$
(6) $$(E_{12}(7))^{-1} = E_{12}(-7) = \begin{bmatrix}1& -7& 0\\ 0& 1& 0\\ 0& 0& 1 \end{bmatrix}$$
(7) $$(E_{12}(7)E_{31}(1))^{-1} = E_{31}(-1)E_{12}(-7) = E_{31}(-1) \begin{bmatrix}1& -7& 0\\ 0& 1& 0\\ 0& 0& 1 \end{bmatrix} = \begin{bmatrix}1& -7& 0\\ 0& 1& 0\\ -1& 7& 1 \end{bmatrix}$$
12. Let $A$ be the following product of $4\times4$ elementary row matrices: $$A=E_{3}(2)E_{14}E_{42}(3).$$ Find $A$ and $A^{-1}$ explicitly.

Solution:
$$A = E_{3}(2)E_{14}\begin{bmatrix}1 &0 &0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 3& 0& 1 \end{bmatrix} = E_{3}(2) \begin{bmatrix}0& 3& 0& 1\\0& 1& 0& 0\\ 0& 0& 1& 0\\1 &0 &0& 0 \end{bmatrix} =\begin{bmatrix}0& 3& 0& 1\\0& 1& 0& 0\\ 0& 0& 2& 0\\1 &0 &0& 0 \end{bmatrix}$$ $$A^{-1}=E_{42}(-3)E_{14}E_{3}({1\over2}) =E_{42}(-3)E_{14}\begin{bmatrix}1 &0 &0& 0\\ 0& 1& 0& 0\\ 0& 0& {1\over2}& 0\\ 0& 0& 0& 1 \end{bmatrix}$$ $$=E_{42}(-3) \begin{bmatrix}0& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& {1\over2}& 0\\1 &0 &0& 0 \end{bmatrix}= \begin{bmatrix}0& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& {1\over2}& 0\\1 &-3 &0& 0 \end{bmatrix}$$
13. Determine which of the following matrices over $\mathbb{Z}_2$ are non-singular and find the inverse, where possible.
(a) $\begin{bmatrix}1& 1& 0& 1\\0& 0& 1& 1\\1& 1& 1& 1\\1& 0& 0& 1 \end{bmatrix}$; (b) $\begin{bmatrix}1& 1& 0& 1\\0& 1& 1& 1\\1& 0& 1& 0\\1& 1& 0& 1 \end{bmatrix}$.

Solution:
In $\mathbb{Z}_2$ field, $1+1=0 \Rightarrow -1 = 1$.
(a) $$\begin{bmatrix}1& 1& 0& 1 & 1& 0& 0& 0\\0& 0& 1& 1 &0& 1& 0& 0\\1& 1& 1& 1& 0& 0& 1& 0\\1& 0& 0& 1& 0& 0& 0& 1 \end{bmatrix}$$ $$\Rightarrow \begin{cases}R_1-R_4\\R_3-R_4 \end{cases}\begin{bmatrix}0& 1& 0& 0 & 1& 0& 0& 1\\0& 0& 1& 1 &0& 1& 0& 0\\0& 1& 1& 0& 0& 0& 1& 1\\1& 0& 0& 1& 0& 0& 0& 1 \end{bmatrix}$$ $$\Rightarrow R_3-R_1 \begin{bmatrix}0& 1& 0& 0 & 1& 0& 0& 1\\0& 0& 1& 1 &0& 1& 0& 0\\0& 0& 1& 0& 1& 0& 1& 0\\1& 0& 0& 1& 0& 0& 0& 1 \end{bmatrix}$$ $$\Rightarrow R_2-R_3 \begin{bmatrix}0& 1& 0& 0 & 1& 0& 0& 1\\0& 0& 0& 1 &1& 1& 1& 0\\0& 0& 1& 0& 1& 0& 1& 0\\1& 0& 0& 1& 0& 0& 0& 1 \end{bmatrix}$$ $$\Rightarrow R_4-R_2 \begin{bmatrix}0& 1& 0& 0 & 1& 0& 0& 1\\0& 0& 0& 1 &1& 1& 1& 0\\0& 0& 1& 0& 1& 0& 1& 0\\1& 0& 0& 0& 1& 1& 1& 1 \end{bmatrix}$$ $$\Rightarrow \begin{cases}R_1\leftrightarrow R_4\\R_2\leftrightarrow R_4^{'} \end{cases} \begin{bmatrix}1& 0& 0& 0& 1& 1& 1& 1\\0& 1& 0& 0 & 1& 0& 0& 1\\0& 0& 1& 0& 1& 0& 1& 0\\0& 0& 0& 1 &1& 1& 1& 0\end{bmatrix}$$ Thus the original matrix is non-singular and its inverse is $$\begin{bmatrix}1& 1& 1& 1\\1& 0& 0& 1\\1& 0& 1& 0\\1& 1& 1& 0\end{bmatrix}$$
(b) $$\begin{bmatrix}1& 1& 0& 1\\0& 1& 1& 1\\1& 0& 1& 0\\1& 1& 0& 1 \end{bmatrix}\Rightarrow R_1-R_4 \begin{bmatrix}0& 0& 0& 0\\0& 1& 1& 1\\1& 0& 1& 0\\1& 1& 0& 1 \end{bmatrix}$$ which is singular matrix.


14. Determine which of the following matrices are non-singular and find the inverse, where possible.
(a) $\begin{bmatrix}1& 1& 1\\-1& 1& 0\\2& 0& 0 \end{bmatrix}$; (b) $\begin{bmatrix}2& 2& 4\\1& 0& 1\\0& 1& 0 \end{bmatrix}$; (c) $\begin{bmatrix}4& 6& -3\\0& 0& 7\\0& 0& 5 \end{bmatrix}$; (d) $\begin{bmatrix}2& 0& 0\\0& -5& 0\\0& 0& 7 \end{bmatrix}$; (e) $\begin{bmatrix}1& 2& 4 & 6\\0& 1& 2 & 0\\0 & 0& 1 & 2\\ 0& 0& 0& 2 \end{bmatrix}$; (f) $\begin{bmatrix}1& 2& 3\\4& 5& 6\\5& 7& 9 \end{bmatrix}$.

Solution:
(a) $$\begin{bmatrix}1& 1& 1& 1& 0& 0\\-1& 1& 0& 0& 1& 0\\2& 0& 0& 0& 0& 1 \end{bmatrix}$$ $$\Rightarrow {1\over2}R_3 \begin{bmatrix}1& 1& 1& 1& 0& 0\\-1& 1& 0& 0& 1& 0\\1& 0& 0& 0& 0& {1\over2} \end{bmatrix}$$ $$\Rightarrow \begin{cases}R_1-R_3\\R_2+R_3 \end{cases} \begin{bmatrix}0& 1& 1& 1& 0& -{1\over2}\\0& 1& 0& 0& 1& {1\over2}\\1& 0& 0& 0& 0& {1\over2} \end{bmatrix}$$ $$\Rightarrow R_1-R_2 \begin{bmatrix}0& 0& 1& 1& -1& -1\\0& 1& 0& 0& 1& {1\over2}\\1& 0& 0& 0& 0& {1\over2} \end{bmatrix}$$ $$\Rightarrow R_1\leftrightarrow R_3 \begin{bmatrix}1& 0& 0& 0& 0& {1\over2} \\0& 1& 0& 0& 1& {1\over2}\\0& 0& 1& 1& -1& -1\end{bmatrix}$$ Thus it is non-singular and its inverse is $$\begin{bmatrix} 0& 0& {1\over2} \\0& 1& {1\over2}\\1& -1& -1\end{bmatrix}.$$
(b) $$\begin{bmatrix}2& 2& 4& 1& 0& 0\\1& 0& 1& 0& 1& 0\\0& 1& 0& 0& 0& 1\end{bmatrix}$$ $$\Rightarrow R_1-2R_2 \begin{bmatrix}0& 2& 2& 1& -2& 0\\1& 0& 1& 0& 1& 0\\0& 1& 0& 0& 0& 1\end{bmatrix}$$ $$\Rightarrow R_1-2R_3 \begin{bmatrix}0& 0& 2& 1& -2& -2\\1& 0& 1& 0& 1& 0\\0& 1& 0& 0& 0& 1\end{bmatrix}$$ $$\Rightarrow {1\over2}R_1 \begin{bmatrix}0& 0& 1& {1\over2}& -1& -1\\1& 0& 1& 0& 1& 0\\0& 1& 0& 0& 0& 1\end{bmatrix}$$ $$\Rightarrow R_2-R_1 \begin{bmatrix}0& 0& 1& {1\over2}& -1& -1\\1& 0& 0& -{1\over2}& 2& 1\\0& 1& 0& 0& 0& 1\end{bmatrix}$$ $$\Rightarrow \begin{cases}R_1\leftrightarrow R_3\\ R_1^{'}\leftrightarrow R_2\end{cases} \begin{bmatrix}1& 0& 0& -{1\over2}& 2& 1\\0& 1& 0& 0& 0& 1\\0& 0& 1& {1\over2}& -1& -1\end{bmatrix}$$ Thus it is non-singular and its inverse is $$\begin{bmatrix}-{1\over2}& 2& 1\\0& 0& 1\\{1\over2}& -1& -1\end{bmatrix}.$$
(c) $$\begin{bmatrix}4& 6& -3\\0& 0& 7\\0& 0& 5 \end{bmatrix}\Rightarrow R_2-{7\over5}R_3 \begin{bmatrix}4& 6& -3\\0& 0& 0\\0& 0& 5 \end{bmatrix}$$ which is singular matrix.
(d) $$\begin{bmatrix}2& 0& 0& 1& 0& 0\\0& -5& 0& 0& 1& 0\\0& 0& 7& 0& 0& 1 \end{bmatrix}$$ $$\Rightarrow\begin{cases}{1\over2}R_1\\-{1\over5}R_2\\{1\over7}R_3\end{cases} \begin{bmatrix}1& 0& 0& {1\over2}& 0& 0\\0& 1& 0& 0& -{1\over5}& 0\\0& 0& 1& 0& 0& {1\over7} \end{bmatrix}$$ Thus it is non-singular and its inverse is $$\begin{bmatrix}{1\over2}& 0& 0\\0& -{1\over5}& 0\\0& 0& {1\over7} \end{bmatrix}.$$
(e) $$\begin{bmatrix}1& 2& 4 & 6& 1& 0& 0& 0\\0& 1& 2 & 0& 0& 1& 0& 0\\0 & 0& 1 & 2& 0& 0& 1& 0\\ 0& 0& 0& 2& 0& 0& 0& 1 \end{bmatrix}$$ $$\Rightarrow\begin{cases}R_1-2R_2\\{1\over2}R_4 \end{cases} \begin{bmatrix}1& 0& 0 & 6& 1& -2& 0& 0\\0& 1& 2 & 0& 0& 1& 0& 0\\0 & 0& 1 & 2& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 0& 0& {1\over2} \end{bmatrix}$$ $$\Rightarrow\begin{cases}R_1-6R_4\\R_2-2R_3 \end{cases} \begin{bmatrix}1& 0& 0 & 0& 1& -2& 0& -3\\0& 1& 0 & -4& 0& 1& -2& 0\\0 & 0& 1 & 2& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 0& 0& {1\over2} \end{bmatrix}$$ $$\Rightarrow\begin{cases}R_2+4R_4\\R_3-2R_4 \end{cases} \begin{bmatrix}1& 0& 0 & 0& 1& -2& 0& -3\\0& 1& 0 & 0& 0& 1& -2& 2\\0 & 0& 1 & 0& 0& 0& 1& -1\\ 0& 0& 0& 1& 0& 0& 0& {1\over2} \end{bmatrix}$$ Thus it is non-singular and its inverse is $$\begin{bmatrix}1& -2& 0& -3\\ 0& 1& -2& 2\\ 0& 0& 1& -1\\ 0& 0& 0& {1\over2} \end{bmatrix}.$$
(f) $$\begin{bmatrix}1& 2& 3\\4& 5& 6\\5& 7& 9 \end{bmatrix}\Rightarrow R_3-R_1 \begin{bmatrix}1& 2& 3\\4& 5& 6\\4& 5& 6 \end{bmatrix}\Rightarrow R_2-R_3 \begin{bmatrix}1& 2& 3\\0&0& 0\\4& 5& 6 \end{bmatrix}$$ which is singular matrix.


15. Let $A$ be a non-singular $n\times n$ matrix. Prove that $A^{t}$ is non-singular and that $(A^{t})^{-1}=(A^{-1})^{t}$.

Solution:
$$AA^{-1}=I_n=A^{-1}A\Rightarrow (AA^{-1})^{t}= (I_n)^{t}=(A^{-1}A)^{t}$$ $$\Rightarrow (A^{-1})^{t}A^{t}=I_n=A^{t}(A^{-1})^{t}$$ Thus $A^{t}$ is singular and its inverse is $(A^{-1})^{t}$.


16. Prove that $A=\begin{bmatrix}a& b\\c& d \end{bmatrix}$ has no inverse if $ad-bc=0$.

Solution:
From Problems 2.4 Question 3 we know that $A^2-(a+d)A+(ad-bc)I_2=0$, so if $ad-bc=0$ and suppose that $A^{-1}$ exists, then we have $$A^2=(a+d)A\Rightarrow A=(a+d)I_2$$ $$\Rightarrow \begin{bmatrix}a& b\\c& d \end{bmatrix}=\begin{bmatrix}a+d& 0\\ 0& a+d \end{bmatrix}$$ $$\Rightarrow a=b=c=d=0\Rightarrow ad-bc=0$$ which is contradiction.


17. Prove that the real matrix $A=\begin{bmatrix}1& a& b\\-a& 1& c\\-b& -c& 1 \end{bmatrix}$ is non-singular by proving that $A$ is row-equivalent to $I_3$.

Solution:
$$A=\begin{bmatrix}1& a& b\\-a& 1& c\\-b& -c& 1 \end{bmatrix}$$ $$\Rightarrow \begin{cases}R_2+aR_1\\ R_3+bR_1 \end{cases} \begin{bmatrix}1& a& b\\0& 1+a^2& c+ab\\0& ab-c& 1+b^2 \end{bmatrix}$$ $$\Rightarrow {1\over1+a^2}R_2\begin{bmatrix}1& a& b\\0& 1& {c+ab\over1+a^2}\\0& ab-c& 1+b^2 \end{bmatrix}$$ $$\Rightarrow R_3-(ab-c)R_2\begin{bmatrix}1& a& b\\0& 1& {c+ab\over1+a^2}\\0& 0& 1+b^2-{(ab-c)(c+ab)\over1+a^2} \end{bmatrix}$$ Since $$1+b^2-{(ab-c)(c+ab)\over1+a^2} = 1+b^2+{(c+ab)(c-ab)\over1+a^2}$$ $$={1+a^2+b^2+a^2b^2+c^2-a^2b^2\over1+a^2} = {1+a^2+b^2+c^2\over1+a^2}\neq0$$ Thus $A$ is equivalent to $I_3$ and it is non-singular.


18. If $P^{-1}AP=B$, prove that $P^{-1}A^{n}P=B^{n}$ for $n\geq1$.

Solution:
Use mathematical induction. Suppose that $P^{-1}A^{n}P=B^{n}$, then $$B^{n+1}= (P^{-1}AP)^{n+1}= (P^{-1}AP)^{n}(P^{-1}AP)$$ $$=P^{-1}A^{n}PP^{-1}AP = P^{-1}A^{n}AP=P^{-1}A^{n+1}P$$
19. Let $A=\begin{bmatrix}{2\over3}&{1\over4}\\ {1\over3}&{3\over4} \end{bmatrix}$, $P=\begin{bmatrix}1& 3\\-1& 4 \end{bmatrix}$. Verify that $P^{-1}AP=\begin{bmatrix}{5\over12}&0\\ 0&1 \end{bmatrix}$ and deduce that $$A^{n}={1\over7}\begin{bmatrix}3 &3\\4& 4 \end{bmatrix} + {1\over7}\left({5\over12}\right) ^{n}\begin{bmatrix}4 &-3\\-4& 3 \end{bmatrix}.$$
Solution:
$$\begin{bmatrix}1& 3 &1& 0\\-1& 4& 0& 1\end{bmatrix}$$ $$\Rightarrow R_2+R_1 \begin{bmatrix}1& 3 &1& 0\\0& 7& 1& 1\end{bmatrix}$$ $$\Rightarrow {1\over7}R_2 \begin{bmatrix}1& 3 &1& 0\\0& 1& {1\over7}& {1\over7}\end{bmatrix}$$ $$\Rightarrow R_1-3R_2 \begin{bmatrix}1& 0 &{4\over7}& -{3\over7}\\0& 1& {1\over7}& {1\over7}\end{bmatrix}$$ Thus $P^{-1}={1\over7}\begin{bmatrix}4& -3\\1& 1 \end{bmatrix}$, and $$P^{-1}AP= {1\over7}\begin{bmatrix}4& -3\\1& 1 \end{bmatrix}\cdot \begin{bmatrix}{2\over3}&{1\over4}\\ {1\over3}&{3\over4} \end{bmatrix} \cdot \begin{bmatrix}1& 3\\-1& 4 \end{bmatrix} = {1\over7}\begin{bmatrix}{5\over3}& -{5\over4}\\ 1&1 \end{bmatrix} \cdot \begin{bmatrix}1& 3\\-1& 4 \end{bmatrix}$$ $$={1\over7} \begin{bmatrix}{35\over12}& 0\\0& 7\end{bmatrix} = \begin{bmatrix} {5\over12}&0\\ 0&1 \end{bmatrix}=B$$ From the previous question, we know that $P^{-1}A^{n}P=B^{n}= \begin{bmatrix} \left({5\over12}\right)^{n}&0\\ 0&1^n \end{bmatrix}$. Hence $$A^n=PB^{n}P^{-1}= \begin{bmatrix}1& 3\\-1& 4 \end{bmatrix}\cdot \begin{bmatrix} \left({5\over12}\right)^{n}&0\\ 0&1 \end{bmatrix} \cdot {1\over7}\begin{bmatrix}4& -3\\1& 1 \end{bmatrix}$$ $$={1\over7}\begin{bmatrix}\left({5\over12}\right)^{n}&3\\-\left({5\over12}\right)^{n} &4 \end{bmatrix}\cdot \begin{bmatrix}4& -3\\1& 1 \end{bmatrix}$$ $$={1\over7} \begin{bmatrix}4\cdot\left({5\over12}\right)^{n}+3& -3\cdot \left({5\over12}\right)^{n}+3 \\-4\cdot\left({5\over12}\right)^{n}+4& 3\cdot \left({5\over12}\right)^{n}+4 \end{bmatrix}$$ $$= {1\over7}\begin{bmatrix}3 &3\\4& 4 \end{bmatrix} + {1\over7}\left({5\over12}\right) ^{n}\begin{bmatrix}4 &-3\\-4& 3 \end{bmatrix}$$
20. Let $A=\begin{bmatrix}a& b\\c& d \end{bmatrix}$ be a Markov matrix; that is a matrix whose elements are non-negative and satisfy $a+c=1=b+d$. Also let $P=\begin{bmatrix}b& 1\\c& -1 \end{bmatrix}$. Prove that if $A\neq I_2$ then
(1) $P$ is non-singular and $P^{-1}AP=\begin{bmatrix}1& 0\\ 0& a+d-1 \end{bmatrix}$,
(2) $A^{n}\to{1\over b+c}\begin{bmatrix}b& b\\ c& c \end{bmatrix}$ as $n\to\infty$, if $A\neq \begin{bmatrix}0& 1\\ 1& 0 \end{bmatrix}$.

Solution:
(1) If $P$ is non-singular then $\Delta=-b-c\neq0$. Since $a+c=1$ and all of the elements are non-negative, so $-b-c = -(b+c) \leq0$. If $b+c=0$, then $b=c=0\Rightarrow a=d=1\Rightarrow A=\begin{bmatrix}1& 0\\0& 1 \end{bmatrix} = I_2$. Thus, if $A\neq I_2$ then $P$ is non-singular and $P^{-1}={1\over-b-c} \begin{bmatrix}-1& -1\\-c& b \end{bmatrix}$. Hence $$P^{-1}AP= {1\over-b-c} \begin{bmatrix}-1& -1\\-c& b \end{bmatrix} \cdot \begin{bmatrix}a& b\\c& d \end{bmatrix} \cdot \begin{bmatrix}b& 1\\c& -1 \end{bmatrix}$$ $$= {1\over-b-c}\cdot \begin{bmatrix}-a-c& -b-d\\-ac+bc& -bc+bd \end{bmatrix} \cdot \begin{bmatrix}b& 1\\c& -1 \end{bmatrix}$$ $$= {1\over-b-c}\cdot \begin{bmatrix}-1& -1\\-ac+bc& -bc+bd \end{bmatrix} \cdot \begin{bmatrix}b& 1\\c& -1 \end{bmatrix}$$ $$= {1\over-b-c}\cdot \begin{bmatrix}-b-c& 0\\-abc+b^2c-bc^2+bcd& -ac+bc+bc-bd \end{bmatrix}$$ $$= {1\over-b-c}\cdot \begin{bmatrix}-b-c& 0\\-bc(a-b+c-d)& -ac+b(1-a)+c(1-d)-bd \end{bmatrix}$$ $$= {1\over-b-c}\cdot \begin{bmatrix}-b-c& 0\\0 & (-b-c)(a+d-1) \end{bmatrix}= \begin{bmatrix}1& 0\\ 0& a+d-1 \end{bmatrix}$$
(2) Since $$P^{-1}A^{n}P=(P^{-1}AP)^n = \begin{bmatrix}1& 0\\ 0& (a+d-1)^n \end{bmatrix}$$ Hence $$A^{n} =P \begin{bmatrix}1& 0\\ 0& (a+d-1)^n \end{bmatrix} P^{-1}$$ $$= \begin{bmatrix}b& 1\\c& -1 \end{bmatrix}\cdot \begin{bmatrix}1& 0\\ 0& (a+d-1)^n \end{bmatrix} \cdot {1\over-b-c} \begin{bmatrix}-1& -1\\-c& b \end{bmatrix}$$ Since when $n\to\infty$, $a+d-1\to0$ for $0 < a+d < 2$, otherwise $A= \begin{bmatrix}0& 1\\ 1& 0 \end{bmatrix}$. Thus $$A^{n} = \begin{bmatrix}b& 1\\c& -1 \end{bmatrix}\cdot \begin{bmatrix}1& 0\\ 0& 0 \end{bmatrix} \cdot {1\over-b-c} \begin{bmatrix}-1& -1\\-c& b \end{bmatrix}$$ $$={1\over-b-c} \begin{bmatrix}b& 0\\ c& 0 \end{bmatrix} \cdot \begin{bmatrix}-1& -1\\-c& b \end{bmatrix}$$ $$= {1\over-b-c} \begin{bmatrix}-b& -b\\-c& -c \end{bmatrix} ={1\over b+c} \begin{bmatrix}b& b\\c& c \end{bmatrix}.$$ 21. If $X=\begin{bmatrix}1& 2\\ 3& 4\\ 5& 6 \end{bmatrix}$ and $Y=\begin{bmatrix}-1\\3\\4 \end{bmatrix}$, find $XX^{t}$, $X^{t}X$, $YY^{t}$, $Y^{t}Y$.

Solution:
$X^{t}=\begin{bmatrix}1& 3& 5\\2& 4& 6 \end{bmatrix}$ and $Y^{t}=\begin{bmatrix}-1& 3& 4 \end{bmatrix}$. Note that $A^{t}A$ MUST be symmetric. $$XX^{t} = \begin{bmatrix}1& 2\\ 3& 4\\ 5& 6 \end{bmatrix}\cdot \begin{bmatrix}1& 3& 5\\2& 4& 6 \end{bmatrix} = \begin{bmatrix}5& 11& 17\\ 11& 25 & 39\\ 17& 39& 61 \end{bmatrix}$$ $$X^{t}X = \begin{bmatrix}1& 3& 5\\2& 4& 6 \end{bmatrix} \cdot \begin{bmatrix}1& 2\\ 3& 4\\ 5& 6 \end{bmatrix} = \begin{bmatrix}35& 44\\44& 56 \end{bmatrix}$$ $$YY^{t} = \begin{bmatrix}-1\\3\\4 \end{bmatrix} \cdot \begin{bmatrix}-1& 3& 4 \end{bmatrix} = \begin{bmatrix}1& -3& -4\\ -3& 9 & 12\\ -4& 12& 16 \end{bmatrix}$$ $$Y^{t}Y = \begin{bmatrix}-1& 3& 4 \end{bmatrix} \cdot \begin{bmatrix}-1\\3\\4 \end{bmatrix} = 26$$
22. Prove that the system of linear equations $$\begin{cases}x+2y=4\\ x+y=5\\3x+5y=12 \end{cases}$$ is inconsistent and find a least squares solution of the system.

Solution:
The augmented matrix is $$\begin{bmatrix}1& 2& 4\\1& 1& 5\\3& 5& 12 \end{bmatrix}\Rightarrow \begin{bmatrix}1& 2& 4\\0& -1& 1\\0& -1& 0 \end{bmatrix}\Rightarrow \begin{bmatrix}1& 0& 4\\0& 0& 1\\0& -1& 0 \end{bmatrix}\Rightarrow \begin{bmatrix}1& 0& 0\\0& 1& 0\\0& 0& 1 \end{bmatrix}$$ The last row indicates that this is inconsistent system.
Since $A=\begin{bmatrix}1& 2\\1& 1\\3& 5 \end{bmatrix}$, $X=\begin{bmatrix}x \\ y \end{bmatrix}$, and $B=\begin{bmatrix}4\\5\\12 \end{bmatrix}$. So the normal equation is $$A^{t}AX=A^{t}B$$ $$\Rightarrow \begin{bmatrix}1& 1& 3\\2& 1& 5 \end{bmatrix}\cdot \begin{bmatrix}1& 2\\1& 1\\3& 5 \end{bmatrix} X= \begin{bmatrix}1& 1& 3\\2& 1& 5 \end{bmatrix} \cdot \begin{bmatrix}4\\5\\12 \end{bmatrix}$$ $$\Rightarrow \begin{bmatrix}11& 18\\18& 30 \end{bmatrix}X = \begin{bmatrix}45\\73 \end{bmatrix}$$ $$\Rightarrow \begin{cases}x ={\Delta_1\over\Delta}= {\begin{vmatrix}45& 18\\73& 30 \end{vmatrix}\over \begin{vmatrix}11& 18\\18& 30 \end{vmatrix}} =6\\ y ={\Delta_2\over\Delta} = {\begin{vmatrix}11& 45\\18& 73 \end{vmatrix}\over \begin{vmatrix}11& 18\\18& 30 \end{vmatrix}} =-{7\over6} \end{cases}$$
23. The points $(0, 0)$, $(1, 0)$, $(2, -1)$, $(3, 4)$, $(4, 8)$ are required to lie on a parabola $y = a+bx+cx^2$. Find a least squares solution for $a$, $b$, $c$. Also prove that no parabola passes through these points.

Solution:
The system is $$\begin{cases}a=0\\ a+b+c=0\\ a+2b+4c=-1\\ a+3b+9c=4\\ a+4b+16c=8 \end{cases}$$ That is, $A=\begin{bmatrix} 1& 0& 0\\ 1& 1& 1\\ 1& 2& 4\\ 1& 3& 9\\ 1& 4& 16\end{bmatrix}$, $X=\begin{bmatrix}a\\b\\c \end{bmatrix}$, and $B=\begin{bmatrix}0\\ 0\\ -1\\ 4\\8 \end{bmatrix}$. The normal equation is $$A^{t}AX=A^{t}B$$ $$\Rightarrow \begin{bmatrix}1& 1& 1& 1& 1\\ 0& 1& 2& 3& 4\\ 0& 1& 4& 9& 16 \end{bmatrix} \cdot \begin{bmatrix} 1& 0& 0\\ 1& 1& 1\\ 1& 2& 4\\ 1& 3& 9\\ 1& 4& 16\end{bmatrix}X = \begin{bmatrix}1& 1& 1& 1& 1\\ 0& 1& 2& 3& 4\\ 0& 1& 4& 9& 16 \end{bmatrix} \cdot \begin{bmatrix}0\\ 0\\ -1\\ 4\\8 \end{bmatrix}$$ $$\Rightarrow \begin{bmatrix}5& 10& 30\\ 10& 30& 100\\ 30& 100& 354 \end{bmatrix}X = \begin{bmatrix}11\\ 42\\ 160\end{bmatrix}$$ The augmented matrix is $$\begin{bmatrix}5& 10& 30 & 11\\ 10& 30& 100 &42\\ 30& 100& 354 &160\end{bmatrix}$$ $$\Rightarrow \begin{bmatrix}1& 2& 6& {11\over5}\\ 1& 3& 10& {21\over5}\\1& {10\over3}& {59\over5}& {16\over3} \end{bmatrix} \Rightarrow \begin{bmatrix}1& 2& 6& {11\over5}\\ 0& 1& 4& 2\\0& {4\over3}& {29\over5}& {47\over15} \end{bmatrix}$$ $$\Rightarrow \begin{bmatrix}1& 0& -2& -{9\over5}\\ 0& 1& 4& 2\\0& 0& {7\over15}& {7\over15} \end{bmatrix} \Rightarrow \begin{bmatrix}1& 0& -2& -{9\over5}\\ 0& 1& 4& 2\\0& 0& 1& 1 \end{bmatrix}$$ $$\Rightarrow \begin{bmatrix}1& 0& 0& {1\over5}\\ 0& 1& 0& -2\\0& 0& 1& 1 \end{bmatrix}\Rightarrow \begin{cases}a={1\over5} \\b=-2 \\c=1 \end{cases}$$ Next, for the original system $AX=B$, its augmented matrix is $$\begin{bmatrix} 1& 0& 0& 0\\ 1& 1& 1& 0\\ 1& 2& 4& -1\\ 1& 3& 9 &4 \\ 1& 4& 16 &8\end{bmatrix}$$ $$\Rightarrow \begin{bmatrix} 1& 0& 0& 0\\ 0& 1& 1& 0\\ 0& 2& 4& -1\\ 0& 3& 9 &4 \\ 0& 4& 16 &8\end{bmatrix} \Rightarrow \begin{bmatrix} 1& 0& 0& 0\\ 0& 1& 1& 0\\ 0& 0& 2& -1\\ 0& 0& 6 &4 \\ 0& 0& 12 & 8 \end{bmatrix}$$ $$\Rightarrow \begin{bmatrix} 1& 0& 0& 0\\ 0& 1& 1& 0\\ 0& 0& 2& -1\\ 0& 0& 0 &7 \\ 0& 0& 0 & 0 \end{bmatrix}$$ The last matrix is inconsistent which means no parabola passes through these points.


24. If $A$ is a symmetric $n\times n$ real matrix and $B$ is $n\times m$, prove that $B^{t}AB$ is a symmetric $m\times m$ matrix.

Solution:
$$(B^{t}AB)^{t}= B^{t}A^{t}(B^{t})^{t}=B^{t}A^{t}B = B^{t}AB$$ Thus, $B^{t}AB$ is a symmetric matrix.


25. If $A$ is $m\times n$ and $B$ is $n\times m$, prove that $AB$ is singular if $m > n$.

Solution:
Since $m > n$, so the homogeneous system $BX=0$ has a non-trivial solution $X_0$ (i.e. the number of unknowns is greater than the number of equations). Hence we have $$A(BX_0) = ABX_0 = (AB)X_0 = 0$$ which means $AB$ ($m\times m$ squares) is singular (if the homogeneous system $AX=0$ has a non-trivial solution, then $A$ is singular).


26. Let $A$ and $B$ be $n\times n$. If $A$ or $B$ is singular, prove that $AB$ is also singular.

Solution:
If $B$ is singular, then we know that the homogeneous system $BX = 0$ has a non-trivial solution $X_0$, that is $$A(BX_0)=(AB)X_0=0$$ which means that $AB$ is also singular since $X_0$ is a non-trivial solution.\\
If $A$ is singular, then $A^{t}$ is also singular (see Question 15). So the homogeneous system $A^{t}X=0$ has a non-trivial solution $X_0$, and we have $$B^{t}(A^{t}X_0)=0 \Rightarrow (B^{t}A^{t})X_0=0$$ $$\Rightarrow (AB)^{t}X_0=0$$ which means $(AB)^{t}$ is singular, and thus $AB$ is also singular.