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 = \left[ \begin{array} { c c c } 1 & 2 & 3 \\ 10 & 20 & 31 \\ 11 & 22 & k \end{array} \right]$ and $\mathbf { v } = \left[ \begin{array} { l } x \\ y \\ z \end{array} \right]$, where $k$ is a constant and $x , y , z$ are variables.
Statements
(37) Regardless of the value of $k$, the matrix $A$ is not invertible, i.e., there is no $3 \times 3$ matrix $B$ such that $B A =$ the $3 \times 3$ identity matrix. (38) There is a unique $k$ such that determinant of $A$ is 0. (39) The set of solutions $( x , y , z )$ of the matrix equation $A \mathbf { v } = \left[ \begin{array} { l } 0 \\ 0 \\ 0 \end{array} \right]$ is either a line or a plane containing the origin. (40) If the equation $A \mathbf { v } = \left[ \begin{array} { c } p \\ q \\ r \end{array} \right]$ has a solution, then it must be true that $q = 10 p$.

In the pyramid $P - ABCD$, $PD \perp$ base $ABCD$, $CD \parallel AB$, $AD = DC = CB = 1$, $AB = 2$.
(1) Prove that $BD \perp PA$;
(2) Find the sine of the angle between $PD$ and plane $PAB$.

In the tetrahedron $A B C D$ , $A D \perp C D , A D = C D$ , $\angle A D B = \angle B D C$ , and $E$ is the midpoint of $A C$.
(1) Prove: Plane $B E D \perp$ plane $A C D$ ;
(2) Given $A B = B D = 2 , \angle A C B = 60 ^ { \circ }$ , point $F$ is on $B D$ . When the area of $\triangle A F C$ is minimized, find the volume of the tetrahedron $F - A B C$ .

For every matrix $A$ in $\mathcal{M}_n(\mathbb{K})$, we set $N(A) = \max_{1 \leqslant i \leqslant n}\left(\sum_{j=1}^{n}|a_{i,j}|\right)$. Show that the map $A \mapsto N(A)$ is a sub-multiplicative norm on $\mathcal{M}_n(\mathbb{K})$.

For every matrix $A$ in $\mathcal{M}_n(\mathbb{K})$, we set $N(A) = \max_{1 \leqslant i \leqslant n}\left(\sum_{j=1}^{n}|a_{i,j}|\right)$. Let $Q \in \mathrm{GL}_n(\mathbb{K})$. Show that $A \mapsto \|A\| = N\left(Q^{-1}AQ\right)$ is a sub-multiplicative norm on $\mathcal{M}_n(\mathbb{K})$.

We are given $A$ in $\mathcal{M}_n(\mathbb{C})$, with $\rho(A) < 1$. We want to show that $\lim_{m \rightarrow +\infty} A^m = 0$.
Let $P$ be in $\mathrm{GL}_n(\mathbb{C})$ and let $T$ be upper triangular, such that $A = PTP^{-1}$. We are given $\delta > 0$. We set $\Delta = \operatorname{diag}\left(1, \delta, \ldots, \delta^{n-1}\right)$ and $\widehat{T} = \Delta^{-1}T\Delta$.
Show that $\widehat{T}$ is upper triangular and that we can choose $\delta$ so that $N(\widehat{T}) < 1$.

We are given $A$ in $\mathcal{M}_n(\mathbb{C})$, with $\rho(A) < 1$. Let $P$ be in $\mathrm{GL}_n(\mathbb{C})$ and let $T$ be upper triangular, such that $A = PTP^{-1}$. We are given $\delta > 0$. We set $\Delta = \operatorname{diag}\left(1, \delta, \ldots, \delta^{n-1}\right)$ and $\widehat{T} = \Delta^{-1}T\Delta$.
With the choice of $\delta$ such that $N(\widehat{T}) < 1$, we set $Q = P\Delta$ and we equip $\mathcal{M}_n(\mathbb{C})$ with the norm $M \mapsto \|M\| = N\left(Q^{-1}MQ\right)$.
Show that $\|A\| < 1$ and deduce $\lim_{m \rightarrow +\infty} A^m = 0$.

Let $A$ denote a positive matrix in $\mathcal{M}_n(\mathbb{R})$.
Show that if there exists in $A$ a path from $i$ to $j$, with $i \neq j$, then there exists an elementary path from $i$ to $j$ of length $\ell \leqslant n-1$. Similarly, show that if there exists in $A$ a circuit passing through $i$, then there exists an elementary circuit passing through $i$ of length $\ell \leqslant n$.

Let $A \geqslant 0$ in $\mathcal{M}_n(\mathbb{R})$. Let $i, j$ be in $\llbracket 1, n \rrbracket$. Let $m \geqslant 1$. Show the equivalence of the propositions:

• there exists in $A$ a path with origin $i$, endpoint $j$, of length $m$;
• the entry with indices $i, j$ of $A^m$ (denoted $a_{i,j}^{(m)}$) is strictly positive.

You may proceed by induction on the integer $m \geqslant 1$.

Let $A$ denote a positive matrix in $\mathcal{M}_n(\mathbb{R})$. Let $i, j$ be in $\llbracket 1, n \rrbracket$, and let $\ell$ and $m$ be in $\mathbb{N}^*$. Show the equivalence of the propositions:

• there exists in $A^m$ a path with origin $i$, endpoint $j$, of length $\ell$;
• there exists in $A$ a path with origin $i$, endpoint $j$, of length $m\ell$.

Let $A$ be a primitive matrix in $\mathcal{M}_n(\mathbb{R})$.
Show that for all $i \neq j$ there exists in $A$ an elementary path from $i$ to $j$ of length $\ell \leqslant n-1$, and that for all $i$ there exists in $A$ an elementary circuit passing through $i$ of length $\ell \leqslant n$.

Give a simple example of a square matrix that is primitive but not strictly positive.

Let $B > 0$ in $\mathcal{M}_n(\mathbb{R})$ and $x \geqslant 0$ in $\mathbb{R}^n$ with $x \neq 0$. Show that $Bx > 0$.

Let $A$ be a primitive matrix and $m \in \mathbb{N}^*$ such that $A^m > 0$. Show that $\forall p \geqslant m, A^p > 0$. You may note, by justifying it, that none of the columns $c_1, c_2, \ldots, c_n$ of $A$ is zero.

Prove that if $A$ is primitive, then $A^k$ is primitive for all $k \geqslant 1$.

Show that the spectral radius of a primitive matrix is strictly positive.

We define the matrix $W_n = (w_{i,j})$ in $\mathcal{M}_n(\mathbb{R})$ by $w_{i,j} = \begin{cases} 1 & \text{if } 1 \leqslant i < n \text{ and } j = i+1 \\ 1 & \text{if } i = n \text{ and } j \in \{1,2\} \\ 0 & \text{in all other cases} \end{cases}$
Show that the characteristic polynomial of $W_n$ is $X^n - X - 1$.
Deduce that $W_n^{n^2-2n+1} = \sum_{k=1}^{n-1} \binom{n-2}{k-1} W_n^k$, then that $W_n^{n^2-2n+2} = I_n + W_n + \sum_{k=2}^{n-1} \binom{n-2}{k-2} W_n^k$.

We define the matrix $W_n = (w_{i,j})$ in $\mathcal{M}_n(\mathbb{R})$ by $w_{i,j} = \begin{cases} 1 & \text{if } 1 \leqslant i < n \text{ and } j = i+1 \\ 1 & \text{if } i = n \text{ and } j \in \{1,2\} \\ 0 & \text{in all other cases} \end{cases}$
Specify the shortest circuit passing through index 1 in the matrix $W_n$.
Deduce that the positive matrix $W_n^{n^2-2n+1}$ is not strictly positive.

We define the matrix $W_n = (w_{i,j})$ in $\mathcal{M}_n(\mathbb{R})$ by $w_{i,j} = \begin{cases} 1 & \text{if } 1 \leqslant i < n \text{ and } j = i+1 \\ 1 & \text{if } i = n \text{ and } j \in \{1,2\} \\ 0 & \text{in all other cases} \end{cases}$
Show that for all $i, j$ in $\llbracket 1, n \rrbracket$, with $i \neq j$, there exists in $W_n$ at least one path with origin $i$, endpoint $j$, and length less than or equal to $n-1$.
You may treat successively the two cases $1 \notin \{i,j\}$ and $1 \in \{i,j\}$.
Deduce that the matrix $W_n^{n^2-2n+2}$ is strictly positive and conclude.

Throughout this subsection, $A$ is a given primitive matrix in $\mathcal{M}_n(\mathbb{R})$. We denote by $\ell \in \llbracket 1, n \rrbracket$ the smallest length of an elementary circuit of $A$.
By contradiction, we suppose $\ell = n$.
Show that then all circuits of $A$ have length a multiple of $n$. Deduce that the matrices $A^{kn+1}$ (with $k \in \mathbb{N}$) have zero diagonal and reach a contradiction.

Throughout this subsection, $A$ is a given primitive matrix in $\mathcal{M}_n(\mathbb{R})$. According to what precedes, there exists in $A$ an elementary circuit $\mathcal{C}$ of length $\ell \leqslant n-1$. To simplify the exposition, and because it does not affect the generality of the problem, we assume that it is the circuit $1 \rightarrow 2 \rightarrow \ldots \rightarrow \ell-1 \rightarrow \ell \rightarrow 1$ (the remaining $n-\ell$ indices $\ell+1, \ell+2, \ldots, n$ being thus located ``outside'' the circuit $\mathcal{C}$).
We will show that $A^{n+\ell(n-2)}$ is strictly positive. For this, we are given $i$ and $j$ in $\llbracket 1, n \rrbracket$. Everything comes down to establishing that there exists in $A$ a path with origin $i$, endpoint $j$ and length $n + \ell(n-2)$.
a) Show that in $A$, we can form a path with origin $i$, of length $n-\ell$, whose endpoint is in $\{1, 2, \ldots, \ell\}$ (we will denote by $k$ this endpoint). You may treat the case $1 \leqslant i \leqslant \ell$, then the case $\ell+1 \leqslant i \leqslant n$.
b) State the reason why the first $\ell$ diagonal coefficients of $A^\ell$ (and in particular the $k$-th) are strictly positive. Show then that there exists a path of length $n-1$ in $A^\ell$ (that is, a path of length $\ell(n-1)$ in $A$) with origin $k$ and endpoint $j$.
c) Finally deduce $A^{n+\ell(n-2)} > 0$, then $A^{n^2-2n+2} > 0$.

For any primitive matrix $A$ in $\mathcal{M}_n(\mathbb{R})$, the spectral radius $\rho(A)$ is a dominant eigenvalue of $A$ and the associated eigenspace is a line that possesses a strictly positive direction vector $x > 0$. We denote $r$ the spectral radius of $A$. We denote $x$ (respectively $y$) a strictly positive direction vector of the line $D = \operatorname{Ker}(A - rI_n)$ (respectively of the line $\Delta = \operatorname{Ker}(A^\top - rI_n)$). We denote $H = \operatorname{Im}(A - rI_n)$.
Show that $H$ is the hyperplane orthogonal to the line $\Delta$ (that is $H = \Delta^\perp$).

For any primitive matrix $A$ in $\mathcal{M}_n(\mathbb{R})$, the spectral radius $\rho(A)$ is a dominant eigenvalue of $A$ and the associated eigenspace is a line that possesses a strictly positive direction vector $x > 0$. We denote $r$ the spectral radius of $A$. We denote $x$ (respectively $y$) a strictly positive direction vector of the line $D = \operatorname{Ker}(A - rI_n)$ (respectively of the line $\Delta = \operatorname{Ker}(A^\top - rI_n)$). We denote $H = \operatorname{Im}(A - rI_n)$. If necessary by multiplying $y$ by an appropriate strictly positive coefficient, we assume $(y \mid x) = y^\top x = 1$. We denote $L = xy^\top$.
Prove that $L$ is the matrix, in the canonical basis, of the projection of $\mathbb{R}^n$ onto the line $D$, parallel to the hyperplane $H$.

For any primitive matrix $A$ in $\mathcal{M}_n(\mathbb{R})$, the spectral radius $\rho(A)$ is a dominant eigenvalue of $A$ and the associated eigenspace is a line that possesses a strictly positive direction vector $x > 0$. We denote $r$ the spectral radius of $A$. We denote $x$ (respectively $y$) a strictly positive direction vector of the line $D = \operatorname{Ker}(A - rI_n)$ (respectively of the line $\Delta = \operatorname{Ker}(A^\top - rI_n)$). We denote $H = \operatorname{Im}(A - rI_n)$. If necessary by multiplying $y$ by an appropriate strictly positive coefficient, we assume $(y \mid x) = y^\top x = 1$. We denote $L = xy^\top$.
Verify that $L$ has rank 1, that it is strictly positive, and that $L^\top y = y$.