In this part, we assume $n \geqslant 2$. For all $(a_{0}, \ldots, a_{n-1}) \in \mathbb{R}^{n}$, we set $$J(a_{0}, \ldots, a_{n-1}) = \left( \begin{array}{cccc} a_{0} & a_{n-1} & \cdots & a_{1} \\ a_{1} & a_{0} & \cdots & a_{2} \\ \vdots & \vdots & & \vdots \\ a_{n-1} & a_{n-2} & \cdots & a_{0} \end{array} \right)$$ Let $\mathcal{A}$ be the set of matrices of $\mathcal{M}_{n}(\mathbb{R})$ of the form $J(a_{0}, \ldots, a_{n-1})$ where $(a_{0}, \ldots, a_{n-1}) \in \mathbb{R}^{n}$. Let $J \in \mathcal{M}_{n}(\mathbb{R})$ be the matrix canonically associated with the endomorphism $\varphi \in \mathcal{L}(\mathbb{R}^{n})$ defined by $\varphi: e_{j} \mapsto e_{j+1}$ if $j \in \{1, \ldots, n-1\}$ and $\varphi(e_{n}) = e_{1}$, where $(e_{1}, \ldots, e_{n})$ is the canonical basis of $\mathbb{R}^{n}$.
Let $M \in \mathcal{M}_{n}(\mathbb{R})$. Show that $M$ commutes with $J$ if and only if $M$ commutes with every element of $\mathcal{A}$.

In this part, we assume $n \geqslant 2$. For all $(a_{0}, \ldots, a_{n-1}) \in \mathbb{R}^{n}$, we set $$J(a_{0}, \ldots, a_{n-1}) = \left( \begin{array}{cccc} a_{0} & a_{n-1} & \cdots & a_{1} \\ a_{1} & a_{0} & \cdots & a_{2} \\ \vdots & \vdots & & \vdots \\ a_{n-1} & a_{n-2} & \cdots & a_{0} \end{array} \right)$$ Let $\mathcal{A}$ be the set of matrices of $\mathcal{M}_{n}(\mathbb{R})$ of the form $J(a_{0}, \ldots, a_{n-1})$ where $(a_{0}, \ldots, a_{n-1}) \in \mathbb{R}^{n}$. Let $J \in \mathcal{M}_{n}(\mathbb{R})$ be the matrix canonically associated with the endomorphism $\varphi \in \mathcal{L}(\mathbb{R}^{n})$ defined by $\varphi: e_{j} \mapsto e_{j+1}$ if $j \in \{1, \ldots, n-1\}$ and $\varphi(e_{n}) = e_{1}$, where $(e_{1}, \ldots, e_{n})$ is the canonical basis of $\mathbb{R}^{n}$.
Show that $\mathcal{A}$ is a commutative subalgebra of $\mathcal{M}_{n}(\mathbb{R})$.

Throughout this part, $\mathcal{A}$ is a subalgebra of $\mathcal{M}_{n}(\mathbb{R})$ strictly contained in $\mathcal{M}_{n}(\mathbb{R})$ and we denote by $d$ its dimension. Let $\mathcal{A}^{\top} = \{ M^{\top} \mid M \in \mathcal{A} \}$.
Show that $\mathcal{A}^{\top}$ is a subalgebra of $\mathcal{M}_{n}(\mathbb{R})$ of the same dimension as $\mathcal{A}$.

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$.
Construct a symmetric matrix with rational coefficients for which $z$ is an eigenvalue.

We consider a non-zero totally real number $z$. We write $Z ( X ) = X ^ { d } - \left( a _ { d - 1 } X ^ { d - 1 } + \cdots + a _ { 1 } X + a _ { 0 } \right)$ with $d$ minimal and $a_i \in \mathbb{Q}$. We consider the matrix $S$ of size $d \times d$ whose coefficient $( i , j )$ equals $t \left( z ^ { i + j } \right)$, and $P \in \mathrm{GL}_d(\mathbb{Q})$, $q_1, \ldots, q_d \in \mathbb{Q}$, $q_i > 0$ such that $S = P^T \cdot \operatorname{Diag}(q_1, \ldots, q_d) \cdot P$. We set $R = \operatorname{Diag}\left(\sqrt{q_1}, \ldots, \sqrt{q_d}\right) \cdot P$ and $M$ the companion matrix of $Z(X)$.
Construct a symmetric matrix with rational coefficients for which $z$ is an eigenvalue.

We consider the directed graph $G = ( S , A )$ where $$\left\{ \begin{array} { l } S = \{ 1,2,3,4 \} \\ A = \{ ( 1,2 ) , ( 2,1 ) , ( 1,3 ) , ( 3,1 ) , ( 1,4 ) , ( 4,1 ) , ( 2,3 ) , ( 3,2 ) , ( 2,4 ) , ( 4,2 ) , ( 3,4 ) , ( 4,3 ) \} \end{array} \right.$$ We assume that, when the point is on one of the vertices of the graph, it has the same probability of going to each of the three other vertices of the graph. We set $$J _ { 4 } = \left( \begin{array} { l l l l } 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{array} \right)$$ Express the transition matrix $T$ as a function of $J _ { 4 }$ and $I _ { 4 }$.

We model the web by a directed graph with $n$ vertices. For every integer $i \in \llbracket 1 , n \rrbracket$, $\lambda _ { i }$ denotes the number of outgoing edges from page $i$. We assume that no page points to itself. A surfer navigates the web in the following way: when on page $i$,

• if page $i$ points to other pages, he goes randomly, with equal probability, to one of these pages;
• if page $i$ points to no other page, he remains on page $i$.

Verify that the transition matrix associated with this navigation model is the matrix $A = \left( a _ { i , j } \right) _ { 1 \leqslant i , j \leqslant n }$ with $$\left\{ \begin{array} { l } a _ { i , i } = \begin{cases} 1 & \text { if page } i \text { points to no other page } \\ 0 & \text { otherwise } \end{cases} \\ a _ { i , j } = \left\{ \begin{array} { l l } 0 & \text { if } i \nrightarrow j \\ 1 / \lambda _ { i } & \text { if } i \rightarrow j \end{array} \quad \text { for } i \neq j \right. \end{array} \right.$$

We model the web by a directed graph with $n$ vertices. The matrix $A$ is the stochastic matrix described in question 29. We define $$B = ( 1 - \alpha ) A + \frac { \alpha } { n } J _ { n }$$ where $J _ { n }$ is the matrix in $\mathcal { M } _ { n } ( \mathbb { R } )$ whose coefficients are all equal to $1$, $A$ is the stochastic matrix described in question 29 and $\alpha$ is a real number in $] 0,1 [$, called the damping factor.
Show that $B$ is a stochastic matrix whose coefficients are all strictly positive.

We assume that $\Sigma_Y$ satisfies $$\forall i \in \llbracket 1, n \rrbracket, \quad \sigma_{i,i} = \sigma^2 \quad \text{and} \quad \forall (i,j) \in \llbracket 1, n \rrbracket^2, \quad i \neq j \Longrightarrow \sigma_{i,j} = \sigma^2 \gamma$$ where $\sigma$ and $\gamma$ are two strictly positive real numbers. We denote by $J \in \mathcal{M}_n(\mathbb{R})$ the matrix whose coefficients are all equal to 1.
Prove that $\gamma \leqslant 1$ and express $\Sigma_Y$ in terms of $J$.

We denote by $\mathcal { C } _ { J } = \left\{ M \in \mathcal { M } _ { n } ( \mathbb { R } ) \mid J M = M J \right\}$ the centralizer of the matrix $J = \left( \begin{array}{cc} 0 & -I_m \\ I_m & 0 \end{array} \right)$. Show that, for every matrix $M \in \mathcal { M } _ { n } ( \mathbb { R } ) \left( = \mathcal { M } _ { 2 m } ( \mathbb { R } ) \right)$,
$$M \in \mathcal { C } _ { J } \quad \Longleftrightarrow \quad \exists ( U , V ) \in \mathcal { M } _ { m } ( \mathbb { R } ) \times \mathcal { M } _ { m } ( \mathbb { R } ) , \quad M = \left( \begin{array} { c c } U & - V \\ V & U \end{array} \right) .$$

Show that the only real nilpotent and symmetric matrix is the zero matrix.

Show that $S_n^+(\mathrm{R})$ and $S_n^{++}(\mathrm{R})$ are convex subsets of $M_n(\mathrm{R})$. Are they vector subspaces of $M_n(\mathrm{R})$?

Show that $S _ { n } ^ { + } ( \mathbf { R } )$ and $S _ { n } ^ { + + } ( \mathbf { R } )$ are convex subsets of $M _ { n } ( \mathbf { R } )$. Are they vector subspaces of $M _ { n } ( \mathbf { R } )$ ?

Give examples of Hadamard matrices of order 1 and 2.

Show that if $H$ is a Hadamard matrix then any matrix obtained by multiplying a row or column of $H$ by $-1$ or by exchanging two rows or two columns of $H$ is still a Hadamard matrix.

Show that if $H$ is a Hadamard matrix of order $n$ then there exists a Hadamard matrix of order $n$ whose coefficients of the first row are all equal to 1. Deduce that if $n \geq 2$ then $n$ is even.

Show that if $H$ is a Hadamard matrix of order $n$ greater than or equal to 4, then $n$ is a multiple of 4. One may begin by showing that we can assume the first row of $H$ is composed only of 1's and its second row is composed of $n/2$ coefficients equal to 1 then $n/2$ coefficients equal to $-1$.

We denote by $\mathbf{e}$ the matrix of $\mathcal{M}_{n,1}(\mathbb{R})$ whose coefficients are all equal to 1. We denote by $\Omega_n$ the set of symmetric positive matrices of order $n$ such that $M \cdot \mathbf{e} = 0$. We denote by $K$ the application from $\Omega_n$ to $\mathcal{M}_n(\mathbb{R})$ which associates to a matrix $A$ $$K(A) = \mathbf{e} \cdot \mathbf{a}^T + \mathbf{a} \cdot \mathbf{e}^T - 2A$$ where $\mathbf{a}$ is the column matrix of $\mathcal{M}_{n,1}(\mathbb{R})$ whose coefficients are the diagonal coefficients of $A$.
Show that for every matrix $A$ of $\Omega_n$ we have $K(A) \in \Delta_n$.

Let $H$ be a Hadamard matrix of order $n$ with first row constant equal to 1. Let $\lambda_1, \ldots, \lambda_n$ be real numbers such that $$\lambda_1 > 0 \geq \lambda_2 \geq \ldots \geq \lambda_n$$ and $$\sum_{i=1}^{n} \lambda_i = 0.$$ We denote by $U$ the matrix $\frac{1}{\sqrt{n}} H$ and $\Lambda$ the diagonal matrix whose diagonal coefficients are the $\lambda_i$. We finally denote by $D = U^T \Lambda U$.
Show that $D$ is EDM.

We now consider the case where $A \in \mathcal{S}_n(\mathbb{R})$ is symmetric. Let $\mathbf{u} \in \mathbb{R}^n$ be such that $\|\mathbf{u}\| = 1$. We set $B = A + \mathbf{u}\mathbf{u}^T$. Show that $B \in \mathcal{S}_n(\mathbb{R})$.

We denote by $J_n^{(\mathrm{s})}$ the matrix of $\mathcal{M}_n(\mathbb{R})$ defined by $$\forall (i,j) \in \llbracket 1,n \rrbracket^2, \quad J_n^{(\mathrm{S})}(i,j) = \frac{2}{\sqrt{2n+1}} \sin\left(\frac{2\pi ij}{2n+1}\right).$$
Deduce that $J_n^{(\mathrm{s})}$ is a symmetric orthogonal matrix.

For all $k \in \llbracket 1,n \rrbracket$, we denote by $C_{n,k}$ the matrix of $\mathcal{M}_n(\mathbb{R})$ defined by $$\forall (i,j) \in \llbracket 1,n \rrbracket^2, \quad C_{n,k}(i,j) = \begin{cases} 1 & \text{if } (i \in \llbracket 1,k \rrbracket \text{ and } j = i+n-k) \text{ or } (i \in \llbracket k+1,n \rrbracket \text{ and } j = i-k) \\ 0 & \text{otherwise} \end{cases}$$ We note that $C_{n,n} = I_n$. We set $J_n^{(1)} = C_{n,1} + C_{n,n-1}$.
Verify that, in the case where $n = 9$, $J_n^{(1)}$ is the matrix such that, for all $(i,j) \in \llbracket 1,9 \rrbracket^2$, the coefficient with index $(i,j)$ equals 1 if the vertices $i$ and $j$ of the graph are connected by an edge and equals 0 otherwise. This means that each particle interacts only with its two nearest neighbors.

We consider the case where $A \in \mathcal{S}_n(\mathbb{R})$ is symmetric. Let $\mathbf{u} \in \mathbb{R}^n$ be such that $\|\mathbf{u}\| = 1$. We set $B = A + \mathbf{u u}^T$. Show that $B \in \mathcal{S}_n(\mathbb{R})$.

Let $\mathscr { A }$ be the set of all $3 \times 3$ symmetric matrices all of whose entries are either 0 or 1. Five of these entries are 1 and four of them are 0.
The number of matrices in $\mathscr { A }$ is
(A) 12
(B) 6
(C) 9
(D) 3

Let $M$ be a $2 \times 2$ symmetric matrix with integer entries. Then $M$ is invertible if
(A) the first column of $M$ is the transpose of the second row of $M$
(B) the second row of $M$ is the transpose of the first column of $M$
(C) $M$ is a diagonal matrix with nonzero entries in the main diagonal
(D) the product of entries in the main diagonal of $M$ is not the square of an integer