$M$ is a $3 \times 3$ matrix with integer entries. For $M$ we have (Sum of column 2) $= 4 \times$ (sum of column 1). (Sum of column 3) $= 4 \times$ (sum of column 2). (Sum of row $2) = 6 +$ (sum of row $1$). (Sum of row $3) = 6 +$ (sum of row 2).
Statements
(9) The sum of all the entries in $M$ must be divisible by 21. (10) None of the row sums is divisible by 7. (11) One of the column sums must be divisible by 7. (12) None of the column sums is divisible by 6.

Natural numbers are arranged at regular intervals on the sides and vertices of squares with side lengths $1, 3, 5, \cdots, 2 n - 1, \cdots$ as shown in the figure below. In each square, 1 is placed directly above the lower left vertex.
Let the $2 \times 2$ matrices with the natural numbers at the four vertices of each square as components be $A _ { 1 } , A _ { 2 } , A _ { 3 } , \cdots , A _ { n } , \cdots$ in order. For example, $A _ { 1 } = \left( \begin{array} { l l } 1 & 2 \\ 4 & 3 \end{array} \right) , A _ { 2 } = \left( \begin{array} { c c } 3 & 6 \\ 12 & 9 \end{array} \right)$. Find the sum of all components of matrix $A _ { 15 }$. [4 points]

For $n \in \mathbb{N}^*$ and $(i,j) \in \llbracket 1, n \rrbracket^2$, we denote by $h_{i,j}^{(-1,n)}$ the coefficient at position $(i,j)$ of the matrix $H_n^{-1}$ and we denote by $s_n$ the sum of the coefficients of the matrix $H_n^{-1}$, that is: $$s_n = \sum_{1 \leqslant i,j \leqslant n} h_{i,j}^{(-1,n)}$$
Calculate $s_1$, $s_2$ and $s_3$. Conjecture in general the value of $s_n$ as a function of $n$.

For $n \in \mathbb{N}^*$ and $(i,j) \in \llbracket 1, n \rrbracket^2$, we denote by $h_{i,j}^{(-1,n)}$ the coefficient at position $(i,j)$ of the matrix $H_n^{-1}$. For $n \in \mathbb{N}$ and $k \in \llbracket 0; n \rrbracket$, we denote by $\binom{n}{k}$ the binomial coefficient $\binom{n}{k} = \frac{n!}{k!(n-k)!}$. The family $\left(K_p\right)_{p \in \mathbb{N}}$ is the orthonormal family defined in question II.E, and $K_n = \sqrt{2n+1}\,\Lambda_n$ where $\Lambda_n$ is a polynomial with integer coefficients.
Let $n \in \mathbb{N}^*$.
a) Calculate $h_{i,i}^{(-1,n)}$ for all $i \in \llbracket 1; n \rrbracket$; we will give in particular a very simple expression of $h_{1,1}^{(-1,n)}$ and $h_{n,n}^{(-1,n)}$ as a function of $n$.
b) Calculate $h_{i,j}^{(-1,n)}$ for all pairs $(i,j) \in \llbracket 1; n \rrbracket^2$; deduce that the coefficients of $H_n^{-1}$ are integers.
c) Show that $h_{i,j}^{(-1,n)}$ is divisible by 4 for all pairs $(i,j) \in \llbracket 2; n \rrbracket^2$.

Let $U_1, U_2, \cdots, U_n$, $n$ elements of $\mathbb{R}^p$ satisfying $\sum_{i=1}^n U_i = 0$. We define the matrix of squared mutual distances $M = \left(\|U_i - U_j\|^2\right)_{(i,j) \in \llbracket 1,n\rrbracket^2} \in \mathcal{S}_n(\mathbb{R})$. It has been shown that ${}^t UU = -\frac{1}{2}\Phi(M)$.
Deduce, for every pair $(i,j) \in \llbracket 1,n\rrbracket^2$, an expression for the inner product $\langle U_i, U_j\rangle = {}^t U_i U_j$ as a function of $$\alpha_{ij} = -\frac{1}{n}\left(S(M)_i + S(M)_j\right) + \frac{1}{n^2}\sigma(M)$$ and of $m_{ij}$ (Torgerson relation).

We consider four points $U_1, U_2, U_3, U_4$ in $\mathbb{R}^3$ satisfying $U_1U_2 = U_2U_3 = U_3U_4 = U_4U_1 = 1$, $U_1U_3 = a$ and $U_2U_4 = b$. We use the notations of the previous parts with $n = 4$.
We set $M = \left(\|U_i - U_j\|^2\right)_{(i,j) \in \llbracket 1,4\rrbracket^2} \in \mathcal{S}_4(\mathbb{R})$.
Write the matrix $M$ then calculate $S(M)$ and $\sigma(M)$.

Let $f$ be a linear form on $\mathcal{M}_n(\mathbb{R})$.
Show that there exists a unique matrix $A \in \mathcal{M}_n(\mathbb{R})$ such that $\forall M \in \mathcal{M}_n(\mathbb{R}), f(M) = \operatorname{Tr}(AM)$.

In this question, $f$ denotes the linear form defined by $\forall M \in \mathcal{M}_n(\mathbb{R}), f(M) = \sum_{j=1}^n \sum_{i=j}^n m_{i,j}$.
Determine the matrix $A$ such that $\forall M \in \mathcal{M}_n(\mathbb{R}), f(M) = \operatorname{Tr}(AM)$.

Let $n \in \mathbb{N}^*$. Let $A \in M_2(\mathbb{R})$ be an antisymmetric matrix. We set $A = \begin{pmatrix} 0 & -\alpha \\ \alpha & 0 \end{pmatrix}$ where $\alpha \in \mathbb{R}$.
Determine a real number $\theta_n$ such that $$\frac{1}{\beta_n}\left(I_2 + \frac{1}{n}A\right) = \begin{pmatrix} \cos\theta_n & -\sin\theta_n \\ \sin\theta_n & \cos\theta_n \end{pmatrix}$$

We are given a matrix $S \in \mathbf{S}_n$, an angle $\theta \in \left]-\frac{\pi}{2}, \frac{\pi}{2}\right[$ and integers $1 \leqslant p < q \leqslant n$ such that $s_{pq} \neq 0$. We define $S' = {}^t R_{p,q}(\theta) S R_{p,q}(\theta)$ and denote its coefficients by $s_{ij}'$.
Show that $s_{qq}' + s_{pp}' = s_{qq} + s_{pp}$.

We are given a matrix $S \in \mathbf{S}_n$, an angle $\theta \in \left]-\frac{\pi}{2}, \frac{\pi}{2}\right[$ and integers $1 \leqslant p < q \leqslant n$ such that $s_{pq} \neq 0$. We define $S' = {}^t R_{p,q}(\theta) S R_{p,q}(\theta)$ and denote its coefficients by $s_{ij}'$.
Express the coefficients $s_{ij}'$ of $S'$ in terms of those of $S$.

We are given a matrix $S \in \mathbf{S}_n$, an angle $\theta \in \left]-\frac{\pi}{2}, \frac{\pi}{2}\right[$ and integers $1 \leqslant p < q \leqslant n$ such that $s_{pq} \neq 0$. We define $S' = {}^t R_{p,q}(\theta) S R_{p,q}(\theta)$ and denote its coefficients by $s_{ij}'$.
Show that the coefficients of $S'$ are expressed uniquely in terms of those of $S$ and the root ($t_0$ or $t_1$) that we have chosen.

We are given a matrix $S \in \mathbf{S}_n$, an angle $\theta \in \left]-\frac{\pi}{2}, \frac{\pi}{2}\right[$ and integers $1 \leqslant p < q \leqslant n$ such that $s_{pq} \neq 0$. We define $S' = {}^t R_{p,q}(\theta) S R_{p,q}(\theta)$ and denote its coefficients by $s_{ij}'$.
By calculating $\left(s_{qq}' - s_{pp}'\right)^2 - \left(s_{qq} - s_{pp}\right)^2$, show that $$\left|s_{qq}' - s_{pp}'\right| \geqslant \left|s_{qq} - s_{pp}\right|$$

We are given a matrix $S \in \mathbf{S}_n$, an angle $\theta \in \left]-\frac{\pi}{2}, \frac{\pi}{2}\right[$ and integers $1 \leqslant p < q \leqslant n$ such that $s_{pq} \neq 0$. We define $S' = {}^t R_{p,q}(\theta) S R_{p,q}(\theta)$ and denote its coefficients by $s_{ij}'$.
From now on, and until the end of the problem, we choose the root $t_0$ of (1) and thus the angle $\theta_0$, mentioned in Question 8b.
(a) Show that $s_{pp} - s_{pp}'$ and $s_{qq}' - s_{qq}$ have the same sign as $s_{qq} - s_{pp}$.
(b) If $1 \leqslant i \leqslant n$, show that $$\left|s_{ii} - s_{qq}'\right| + \left|s_{ii} - s_{pp}'\right| - \left|s_{ii} - s_{pp}\right| - \left|s_{ii} - s_{qq}\right| \geqslant 0$$

Give the matrix $M = \left(M_{i,j}\right)_{1 \leqslant i,j \leqslant n+1}$ of $\tau$ in the basis $\left(P_k\right)_{k \in \llbracket 1, n+1 \rrbracket}$. Express the coefficients $M_{i,j}$ in terms of $i$ and $j$.

We are given a real sequence $\left(u_k\right)_{k \in \mathbb{N}}$ and we define for every integer $k \in \mathbb{N}$ $$v_k = \sum_{j=0}^{k} \binom{k}{j} u_j$$ Determine a matrix $Q \in \mathcal{M}_{n+1}(\mathbb{R})$ such that $$\left(\begin{array}{c} v_0 \\ v_1 \\ \vdots \\ v_n \end{array}\right) = Q \left(\begin{array}{c} u_0 \\ u_1 \\ \vdots \\ u_n \end{array}\right)$$

We fix $n \in \mathbb { N }$. We define the linear map: $$\begin{aligned} \Delta : \mathbb { R } [ X ] & \rightarrow \mathbb { R } [ X ] \\ P ( X ) & \mapsto P ( X + 1 ) - P ( X ) \end{aligned}$$ We define $H _ { 0 } ( X ) = 1$ and, for all $k \in \mathbb { N } ^ { * }$, $H _ { k } ( X ) = X ( X - 1 ) \cdots ( X - k + 1 )$.
Let $\Delta _ { n }$ be the endomorphism induced by $\Delta$ on the stable subspace $\mathbb { R } _ { n } [ X ]$. Determine the matrix $A$ of $\Delta _ { n }$ in the basis $( H _ { 0 } , \ldots , H _ { n } )$.

Show that for every matrix $A$ in $\mathcal{M}_{n}(\{-1,1\})$, the set $S(A)$ is included in $\{-n^{2}, \ldots, n^{2}\}$. Show that the inclusion is strict (one may think of a parity argument), and show that $S(A)$ is a symmetric set, in the sense that an integer $k$ is in $S(A)$ if and only if $-k$ is in $S(A)$.

For $A = (a_{i,j})_{1 \leqslant i,j \leqslant n} \in \mathcal{M}_{n}(\{-1,1\})$ and $Y = (y_{i})_{1 \leqslant i \leqslant n} \in \{-1,1\}^{n}$, we denote $$g_{A}(Y) = \max\left\{{}^{t}X A Y \mid X \in \{-1,1\}^{n}\right\}.$$
Show that the function $g_{A}$ can be rewritten as $$g_{A}(Y) = \sum_{i=1}^{n} \left|\sum_{j=1}^{n} a_{i,j} y_{j}\right|.$$

Give the expression of $\langle A , B \rangle _ { F }$ as a function of the coefficients of $A$ and $B$.

We denote by $\mathscr { R }$ the set of totally real numbers and we admit that there exists a function $t : \mathscr { R } \rightarrow \mathbb { Q }$ satisfying the following two properties: (i) for $x , y \in \mathscr { R }$ and $\lambda , \mu \in \mathbb { Q }$, we have $t ( \lambda x + \mu y ) = \lambda t ( x ) + \mu t ( y )$ (ii) for $x$ totally positive, we have $t ( x ) \geqslant 0$ and the equality is strict if $x \neq 0$.
We consider a non-zero totally real number $z$. By definition, there exists a monic polynomial $Z ( X ) \in \mathbb { Q } [ X ]$ that annihilates $z$. We write $Z ( X )$ in the form: $$Z ( X ) = X ^ { d } - \left( a _ { d - 1 } X ^ { d - 1 } + \cdots + a _ { 1 } X + a _ { 0 } \right)$$ with $d \in \mathbb{N} ^ { * }$ and $a _ { i } \in \mathbb { Q }$ for all $i \in \{ 0 , \ldots , d - 1 \}$. We further assume that $Z ( X )$ is chosen so that $d$ is minimal among the degrees of monic polynomials $P ( X ) \in \mathbb{Q} [ X ]$ such that $P ( z ) = 0$. We consider the matrix $S$ of size $d \times d$ whose coefficient $(i, j)$, $1 \leqslant i , j \leqslant d$, equals $t ( z ^ { i + j } )$. For $X , Y \in \mathbb { R } ^ { d }$, we set $B ( X , Y ) = X ^ { T } S Y$.
13a. Show that $B ( X , X ) > 0$ for $X \in \mathbb { Q } ^ { d }$, $X \neq 0$.
13b. Deduce that the matrix $S$ is invertible.

We denote by $\mathscr { R }$ the set of totally real numbers and we admit that there exists a function $t : \mathscr { R } \rightarrow \mathbb { Q }$ satisfying the following two properties: (i) for $x , y \in \mathscr { R }$ and $\lambda , \mu \in \mathbb { Q }$, we have $t ( \lambda x + \mu y ) = \lambda t ( x ) + \mu t ( y )$ (ii) for $x$ totally positive, we have $t ( x ) \geqslant 0$ and the equality is strict if $x \neq 0$.
We consider a non-zero totally real number $z$. By definition, there exists a monic polynomial $Z ( X ) \in \mathbb { Q } [ X ]$ that annihilates $z$. We write $Z ( X )$ in the form: $$Z ( X ) = X ^ { d } - \left( a _ { d - 1 } X ^ { d - 1 } + \cdots + a _ { 1 } X + a _ { 0 } \right)$$ with $d \in \mathbb{N} ^ { * }$ and $a _ { i } \in \mathbb { Q }$ for all $i \in \{ 0 , \ldots , d - 1 \}$. We further assume that $Z ( X )$ is chosen so that $d$ is minimal among the degrees of monic polynomials $P ( X ) \in \mathbb{Q} [ X ]$ such that $P ( z ) = 0$. We consider the matrix $S$ of size $d \times d$ whose coefficient $(i, j)$, $1 \leqslant i , j \leqslant d$, equals $t ( z ^ { i + j } )$. For $X , Y \in \mathbb { R } ^ { d }$, we set $B ( X , Y ) = X ^ { T } S Y$.
Show that $B$ is an inner product on $\mathbb { R } ^ { d }$.

Show that $$\|A - B\|_{F}^{2} = \sum_{1 \leqslant i,j \leqslant n} p_{i,j}^{2}\left(\lambda_{i}(A) - \lambda_{j}(B)\right)^{2}.$$

We now assume that all coefficients $m _ { i , j } ( 1 \leqslant i , j \leqslant n )$ of the stochastic matrix $M$ are strictly positive. We set $\varepsilon = \min _ { 1 \leqslant i , j \leqslant n } m _ { i , j }$. We are interested in the sequence $\left( M ^ { k } \right) _ { k \in \mathbb { N } }$ of powers of $M$. We denote by $m _ { i , j } ^ { ( k ) }$ the coefficient of the matrix $M ^ { k }$ located in row $i$ and column $j$.
For all $j \in \llbracket 1 , n \rrbracket$, we set $$\left\{ \begin{array} { l } \alpha _ { j } ^ { ( k ) } = \min _ { 1 \leqslant i \leqslant n } m _ { i , j } ^ { ( k ) } , \\ \beta _ { j } ^ { ( k ) } = \max _ { 1 \leqslant i \leqslant n } m _ { i , j } ^ { ( k ) } . \end{array} \right.$$
In the following four questions, $j$ is a fixed integer in $\llbracket 1 , n \rrbracket$ and $k$ is fixed in $\mathbb { N }$. Prove that there exists a pair $\left( i _ { 0 } , j _ { 0 } \right) \in \llbracket 1 , n \rrbracket ^ { 2 }$ such that $$\alpha _ { j } ^ { ( k + 1 ) } - \alpha _ { j } ^ { ( k ) } \geqslant m _ { i _ { 0 } , j _ { 0 } } \left( \beta _ { j } ^ { ( k ) } - \alpha _ { j } ^ { ( k ) } \right) .$$

We now assume that all coefficients $m _ { i , j } ( 1 \leqslant i , j \leqslant n )$ of the stochastic matrix $M$ are strictly positive. We set $\varepsilon = \min _ { 1 \leqslant i , j \leqslant n } m _ { i , j }$. We are interested in the sequence $\left( M ^ { k } \right) _ { k \in \mathbb { N } }$ of powers of $M$. We denote by $m _ { i , j } ^ { ( k ) }$ the coefficient of the matrix $M ^ { k }$ located in row $i$ and column $j$.
For all $j \in \llbracket 1 , n \rrbracket$, we set $$\left\{ \begin{array} { l } \alpha _ { j } ^ { ( k ) } = \min _ { 1 \leqslant i \leqslant n } m _ { i , j } ^ { ( k ) } , \\ \beta _ { j } ^ { ( k ) } = \max _ { 1 \leqslant i \leqslant n } m _ { i , j } ^ { ( k ) } . \end{array} \right.$$
In the following four questions, $j$ is a fixed integer in $\llbracket 1 , n \rrbracket$ and $k$ is fixed in $\mathbb { N }$. Prove that there exists a pair $\left( i _ { 1 } , j _ { 1 } \right) \in \llbracket 1 , n \rrbracket ^ { 2 }$ such that $$\beta _ { j } ^ { ( k ) } - \beta _ { j } ^ { ( k + 1 ) } \geqslant m _ { i _ { 1 } , j _ { 1 } } \left( \beta _ { j } ^ { ( k ) } - \alpha _ { j } ^ { ( k ) } \right) .$$