Exercise 2 — Candidates who have followed the specialization course
We are given the matrices $M = \left( \begin{array} { c c c } 1 & 1 & 1 \\ 1 & - 1 & 1 \\ 4 & 2 & 1 \end{array} \right)$ and $I = \left( \begin{array} { l l l } 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right)$.

Part A

1. Determine the matrix $M ^ { 2 }$. We are given $M ^ { 3 } = \left( \begin{array} { c c c } 20 & 10 & 11 \\ 12 & 2 & 9 \\ 42 & 20 & 21 \end{array} \right)$.
2. Verify that $M ^ { 3 } = M ^ { 2 } + 8 M + 6 I$.
3. Deduce that $M$ is invertible and that $M ^ { - 1 } = \frac { 1 } { 6 } \left( M ^ { 2 } - M - 8 I \right)$.

Part B Study of a particular case

We seek to determine three integers $a , b$ and $c$ such that the parabola with equation $y = a x ^ { 2 } + b x + c$ passes through the points $\mathrm { A } ( 1 ; 1 ) , \mathrm { B } ( - 1 ; - 1 )$ and $\mathrm { C } ( 2 ; 5 )$.

1. Prove that the problem amounts to finding three integers $a , b$ and $c$ such that $$M \left( \begin{array} { l } a \\ b \\ c \end{array} \right) = \left( \begin{array} { c } 1 \\ - 1 \\ 5 \end{array} \right)$$
2. Calculate the numbers $a$, $b$ and $c$ and verify that these numbers are integers.

Part C Return to the general case

The numbers $a , b , c , p , q , r$ are integers. In a frame ( $\mathrm { O } , \vec { \imath } , \vec { \jmath }$ ), we consider the points $\mathrm { A } ( 1 ; p ) , \mathrm { B } ( - 1 ; q )$ and $\mathrm { C } ( 2 ; r )$. We seek values of $p , q$ and $r$ for which there exists a parabola with equation $y = a x ^ { 2 } + b x + c$ passing through A, B and C.

1. Prove that if $\left( \begin{array} { l } a \\ b \\ c \end{array} \right) = M ^ { - 1 } \left( \begin{array} { c } p \\ q \\ r \end{array} \right)$ with $a , b$ and $c$ integers, then $$\begin{cases} - 3 p + q + 2 r & \equiv 0 [ 6 ] \\ 3 p - 3 q & \equiv 0 [ 6 ] \\ 6 p + 2 q - 2 r & \equiv 0 [ 6 ] \end{cases}$$
2. Deduce that $\left\{ \begin{array} { l l l } q - r & \equiv & 0 [ 3 ] \\ p - q & \equiv & 0 [ 2 ] \end{array} \right.$.
3. Conversely, we admit that if $\left\{ \begin{array} { l } q - r \equiv 0 [ 3 ] \\ p - q \equiv 0 [ 2 ] \\ \mathrm { A } , \mathrm { B } , \mathrm { C } \text{ are not collinear} \end{array} \right.$ then there exist three integers $a , b$ and $c$ such that the parabola with equation $y = a x ^ { 2 } + b x + c$ passes through the points $\mathrm { A } , \mathrm { B }$ and C. a. Show that the points $\mathrm { A } , \mathrm { B }$ and C are collinear if and only if $2 r + q - 3 p = 0$. b. We choose $p = 7$. Determine integers $q , r , a , b$ and $c$ such that the parabola with equation $y = a x ^ { 2 } + b x + c$ passes through the points $\mathrm { A } , \mathrm { B }$ and C.

Let $A$ be a $3 \times 3$ real matrix such that $A\begin{pmatrix}0\\1\\0\end{pmatrix} = \begin{pmatrix}2\\0\\0\end{pmatrix}$, $A\begin{pmatrix}0\\0\\1\end{pmatrix} = \begin{pmatrix}4\\0\\0\end{pmatrix}$, $A\begin{pmatrix}1\\1\\1\end{pmatrix} = \begin{pmatrix}2\\1\\1\end{pmatrix}$. Then, the system $(A - 3I)\begin{pmatrix}x\\y\\z\end{pmatrix} = \begin{pmatrix}1\\2\\3\end{pmatrix}$ has
(1) unique solution
(2) exactly two solutions
(3) no solution
(4) infinitely many solutions

Problem 2
Consider the column vectors $\mathbf { a } _ { 1 } = \left( \begin{array} { l } 0 \\ 1 \\ 1 \end{array} \right) , \mathbf { a } _ { 2 } = \left( \begin{array} { l } 1 \\ 0 \\ 1 \end{array} \right) , \mathbf { a } _ { 3 } = \left( \begin{array} { l } 1 \\ 1 \\ 0 \end{array} \right) , \mathbf { b } = \left( \begin{array} { l } 1 \\ 2 \\ 4 \end{array} \right) , \mathbf { 0 } = \left( \begin{array} { l } 0 \\ 0 \\ 0 \end{array} \right)$.
I. When $\mathbf { A } = \left( \begin{array} { l l l } \mathbf { a } _ { 1 } & \mathbf { a } _ { 2 } & \mathbf { a } _ { 3 } \end{array} \right)$, obtain the three-dimensional column vector $\mathbf { x }$ which meets
$$A x - b = 0 .$$
II. Any $m \times n$ real matrix $\mathbf { B }$ is expressed using orthonormal matrices $\mathbf { U } ( m \times m )$ and $\mathrm { V } ( n \times n )$ as
$$\mathbf { B } = \mathbf { U \Sigma V } ^ { T } , \quad \boldsymbol { \Sigma } = \left( \begin{array} { c c c c c c c } \sigma _ { 1 } & 0 & \cdots & 0 & 0 & \cdots & 0 \\ 0 & \sigma _ { 2 } & \ddots & \vdots & \vdots & & \vdots \\ \vdots & \ddots & \ddots & 0 & \vdots & & \vdots \\ 0 & \cdots & 0 & \sigma _ { r } & 0 & \cdots & 0 \\ 0 & \cdots & \cdots & 0 & 0 & \cdots & 0 \\ \vdots & & & \vdots & \vdots & & \vdots \\ 0 & \cdots & \cdots & 0 & 0 & \cdots & 0 \end{array} \right) , \quad r = \operatorname { rank } ( \mathbf { B } ) .$$
$\sigma _ { 1 } , \sigma _ { 2 } , \cdots , \sigma _ { r }$ are positive real numbers, and they are called singular values of $\mathbf { B }$. $\mathbf { P } ^ { T }$ means the transposed matrix of a matrix $\mathbf { P }$. Then, express $\mathbf { B B } ^ { T }$ and $\mathbf { B } ^ { T } \mathbf { B }$ using matrices $\mathbf { U } , \mathbf { V } , \boldsymbol { \Sigma }$ and their transposed matrices, respectively.
Let $\mathbf { B } = \left( \mathbf { a } _ { 1 } \mathbf { a } _ { 2 } \right)$ in the following questions.
III. Find the eigenvalues and corresponding eigenvectors for $\mathbf { B B } ^ { T }$.
IV. Find singular values of $\mathbf { B }$ and orthonormal matrices $\mathbf { U }$ and $\mathbf { V }$ used in Equation (2).
V. Find the two-dimensional column vector $\mathbf { x }$ which minimizes the norm
$$\| \mathrm { Bx } - \mathrm { b } \| ^ { 2 } = ( \mathrm { Bx } - \mathrm { b } ) ^ { T } ( \mathrm { Bx } - \mathrm { b } ) .$$

Consider to solve the following simultaneous linear equation:
$$A x = b$$
where $\boldsymbol { A } \in \mathcal { R } ^ { m \times n } , \boldsymbol { b } \in \mathcal { R } ^ { m }$ are a constant matrix and a vector, and $\boldsymbol { x } \in \mathcal { R } ^ { n }$ is an unknown vector. Answer the following questions.
(1) An $m \times ( n + 1 )$ matrix $\overline { \boldsymbol { A } } = ( \boldsymbol { A } \mid \boldsymbol { b } )$ is made by adding a column vector after the last column of matrix $\boldsymbol { A }$. In the case of $\boldsymbol { A } = \left( \begin{array} { c c c } 1 & 0 & - 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{array} \right)$ and $\boldsymbol { b } = \left( \begin{array} { c } 2 \\ 4 \\ 2 \end{array} \right)$, $\overline { \boldsymbol { A } } = \left( \begin{array} { c c c c } 1 & 0 & - 1 & 2 \\ 1 & 1 & 0 & 4 \\ 0 & 1 & 1 & 2 \end{array} \right)$ is obtained. Let the $i$-th column vector of the matrix $\overline { \boldsymbol { A } }$ be $\boldsymbol { a } _ { i } ( i = 1,2,3,4 )$.
(i) Find the maximum number of linearly independent vectors among $\boldsymbol { a } _ { 1 } , \boldsymbol { a } _ { 2 }$ and $\boldsymbol { a } _ { 3 }$.
(ii) Show that $a _ { 4 }$ can be represented as a linear sum of $a _ { 1 } , a _ { 2 }$ and $a _ { 3 }$, by obtaining scalars $x _ { 1 }$ and $x _ { 2 }$ that satisfy $\boldsymbol { a } _ { 4 } = x _ { 1 } \boldsymbol { a } _ { 1 } + x _ { 2 } \boldsymbol { a } _ { 2 } + \boldsymbol { a } _ { 3 }$.
(iii) Find the maximum number of linearly independent vectors among $\boldsymbol { a } _ { 1 } , \boldsymbol { a } _ { 2 } , \boldsymbol { a } _ { 3 }$ and $a _ { 4 }$.
(2) Show that the solution of the simultaneous linear equation exists when $\operatorname { rank } \overline { \boldsymbol { A } } = \operatorname { rank } \boldsymbol { A }$, for arbitrary $m , n , \boldsymbol { A }$ and $\boldsymbol { b }$.
(3) There is no solution when $\operatorname { rank } \overline { \boldsymbol { A } } > \operatorname { rank } \boldsymbol { A }$. When $m > n , \operatorname { rank } \boldsymbol { A } = n$ and $\operatorname { rank } \overline { \boldsymbol { A } } > \operatorname { rank } \boldsymbol { A }$, obtain $\boldsymbol { x }$ that minimizes the squared norm of the difference between the left hand side and the right hand side of the simultaneous linear equation, namely $\| \boldsymbol { b } - \boldsymbol { A } \boldsymbol { x } \| ^ { 2 }$.
(4) When $m < n$ and $\operatorname { rank } \boldsymbol { A } = m$, there exist multiple solutions for the simultaneous linear equation for arbitrary $\boldsymbol { b }$. Obtain $\boldsymbol { x }$ that minimizes $\| \boldsymbol { x } \| ^ { 2 }$ among them, by adopting the method of Lagrange multipliers and using the simultaneous linear equation as the constraint condition.
(5) Show that there exists a unique $\boldsymbol { P } \in \mathcal { R } ^ { n \times m }$ that satisfies the following four equations for arbitrary $m , n$ and $\boldsymbol { A }$.
$$\begin{array} { r } \boldsymbol { A P A } = \boldsymbol { A } \\ \boldsymbol { P A P } = \boldsymbol { P } \\ ( \boldsymbol { A P } ) ^ { T } = \boldsymbol { A P } \\ ( \boldsymbol { P A } ) ^ { T } = \boldsymbol { P A } \end{array}$$
(6) Show that both $\boldsymbol { x }$ obtained in (3) and $\boldsymbol { x }$ obtained in (4) are represented in the form of $x = P b$.

$$\begin{array}{r} 2x + 2y - z = 1 \\ x + y + z = 2 \\ y - z = 1 \end{array}$$
In the solution of the system of equations above, what is $x$?
A) $-3$
B) $-2$
C) $-1$
D) $0$
E) $3$