We define the matrix $Z_n = (z_{i,j}) \in \mathcal{M}_n(\mathbb{R})$ by $z_{i,j} = \begin{cases} 1 & \text{if } 1 \leqslant i < n \text{ and } j = i+1 \\ 1 & \text{if } (i,j) \in \{(n-1,1),(n,2)\} \\ 0 & \text{in all other cases} \end{cases}$
Show that $Z_n^{n^2-2n+2} = 2^{n-1} Z_n$ and recover the fact that $Z_n$ is not primitive.

What is $M^{-1}$? Express the coefficients $\left(M^{-1}\right)_{i,j}$ in terms of $i$ and $j$.

Let $M \in M_n(\mathbb{R})$ be an invertible matrix with integer coefficients.
1a. Show that $M^{-1}$ has rational coefficients.
1b. Show the equivalence of the following propositions:
i) $M^{-1}$ has integer coefficients.
ii) $\det M$ equals 1 or $-1$.

Let $x , y$ be strictly positive vectors of $\mathbb { R } ^ { n }$ and let $S , R$ be two sign diagonal matrices.
(a) Show that $$( S x \mid R y ) \leq ( x \mid y )$$ with equality if and only if $R = S$.
(b) Prove the uniqueness of $S$ in Broyden's theorem.
(c) Show that $$\| S x + R y \| \leq \| x + y \|$$ with equality if and only if $R = S$.

Let $M = (x_1 | \cdots | x_n) \in \mathrm{GL}_n(\mathbb{R})$.
2a. Show that $M \in \mathrm{GL}_n(\mathbb{Z})$ if and only if $M(\mathbb{Z}^n) = \mathbb{Z}^n$.
2b. Show the equivalence of the following propositions:
i) $M \in \mathrm{GL}_n(\mathbb{Z})$.
ii) The integer points of the parallelepiped $\mathcal{P} = \left\{\sum_{i=1}^n t_i x_i \mid \forall i \in \{1,\ldots,n\}, t_i \in [0,1]\right\}$ are exactly the $2^n$ points $\sum_{i=1}^n \varepsilon_i x_i$, where $\varepsilon_i \in \{0,1\}$ for all $i \in \{1,\ldots,n\}$.

Let $O$ be an orthogonal matrix of $M _ { n } ( \mathbb { R } )$ and $S$ a sign diagonal matrix. Show that the equality $O x = S x$ with $x \in \mathbb { R } ^ { n }$ strictly positive is equivalent to $$( * ) \left\{ \begin{array} { c } \left( I _ { n } + O \right) x \geq 0 \\ \left( I _ { n } - O \right) x \geq 0 \\ x > 0 \end{array} \right.$$

For all $\alpha$ in $\mathbb{R}$ and for all distinct integers $i$ and $j$ between 1 and $n$, describe the effect on a square matrix $M$ of size $n$ of left multiplication by $I_n + \alpha E_{ij}$. Same question for right multiplication.

We assume $n = 2$. We identify elements $x = \binom { x _ { 1 } } { x _ { 2 } } \in \mathbb { R } ^ { 2 }$ with vectors $\vec { x } = x _ { 1 } \vec { i } + x _ { 2 } \vec { j }$ of the Euclidean plane relative to an orthonormal frame $(\Omega , \vec { i } , \vec { j })$.
Let $O$ be the matrix of a reflection relative to a line passing through $\Omega$ and directed by a vector $\vec { v } _ { + }$. Determine a vector $x \in \mathbb { R } ^ { 2 }$ strictly positive and a sign diagonal matrix $S \in M _ { 2 } ( \mathbb { R } )$ such that $O x = S x$. Hint: begin by treating the case where $\vec { v } _ { + } \in \{ \vec { i } , \vec { j } \}$.

Let $n \geqslant 2$ and $a_1, \ldots, a_n$ be integers not all zero. The purpose of this question is to show that there exists a matrix in $M_n(\mathbb{Z})$ whose first column is $(a_1, \ldots, a_n)$ and whose determinant is $\gcd(a_1, \ldots, a_n)$. For this we proceed by induction on $n$.
Let $N \in M_{n-1}(\mathbb{Z})$ be a matrix whose first column is $(a_2, \ldots, a_n)$. Given $u, v \in \mathbb{Q}$, we consider the matrix $$M = \left(\begin{array}{cccc|c} a_1 & 0 & \cdots & 0 & u \\ \hline & & & & va_2 \\ & N & & & va_3 \\ & & & & \vdots \\ & & & & va_n \end{array}\right).$$
4a. Express $\det M$ as a function of $\det N$, $u$ and $v$.
4b. Suppose that $a_2, \ldots, a_n$ are not all zero and that $\det N = \gcd(a_2, \ldots, a_n)$. Show that we can choose $u, v$ so that $M$ answers the question.
4c. Conclude the induction.

We assume $n = 2$. We identify elements $x = \binom { x _ { 1 } } { x _ { 2 } } \in \mathbb { R } ^ { 2 }$ with vectors $\vec { x } = x _ { 1 } \vec { i } + x _ { 2 } \vec { j }$ of the Euclidean plane relative to an orthonormal frame $(\Omega , \vec { i } , \vec { j })$.
Let $O$ be the matrix of a rotation with center $\Omega$ and angle $\theta \in ] - \pi , \pi ]$ nonzero. Using a drawing, find two vectors $x _ { + }$ and $x _ { - }$ such that $$O x _ { + } = \operatorname { diag } ( 1 , - 1 ) x _ { + } \text { and } O x _ { - } = \operatorname { diag } ( - 1,1 ) x _ { - }$$ Then discuss according to the sign of $\theta$, which of $x _ { + }$ and $x _ { - }$ is strictly positive.

Let $M \in M_n(\mathbb{Z})$ with nonzero determinant. We wish to show that there exists a matrix $A$ in $\mathrm{GL}_n(\mathbb{Z})$ such that $MA$ is upper triangular and, denoting $MA = (c_{ij})$, we have the inequalities $0 < c_{11}$ and $0 \leqslant c_{ij} < c_{ii}$ for all $i, j \in \{1, \ldots, n\}$ such that $i < j$.
5a. We denote $M = (x_1 | \cdots | x_n)$. Let $x_1', \ldots, x_n'$ be the elements of $\mathbb{Z}^{n-1}$ obtained by taking the last $(n-1)$ coordinates of $x_1, \ldots, x_n$. Show that there exist $a_1, \ldots, a_n$ in $\mathbb{Q}$, not all zero, such that $\sum_{i=1}^n a_i x_i' = 0$. Show that we can choose the $a_i$ to be integers that are coprime as a set.
5b. Show that there exists a matrix $A_1$ in $\mathrm{GL}_n(\mathbb{Z})$ such that the first column of $\tilde{C} = MA_1$ has all its coefficients $\tilde{c}_{i1}$ zero except the first $\tilde{c}_{11}$ which we can take to be strictly positive.
5c. By considering for all $j = 2, \ldots, n$ the Euclidean division $\tilde{c}_{1j} = q_j \tilde{c}_{11} + r_j$, $0 \leqslant r_j < \tilde{c}_{11}$, show that we can assume $\tilde{c}_{11} > \tilde{c}_{1j}$, if necessary by changing $A_1$.
5d. Conclude by induction.

With the notations of Broyden's theorem, we denote by $M \in M _ { 3 n } ( \mathbb { R } )$ the following block matrix $$M = \left( \begin{array} { c c c } 0 & 0 & I _ { n } + O \\ 0 & 0 & I _ { n } - O \\ - \left( I _ { n } + { } ^ { t } O \right) & - \left( I _ { n } - { } ^ { t } O \right) & 0 \end{array} \right)$$ Using Tucker's theorem, show that there exist positive vectors $x , z _ { 1 } , z _ { 2 } \in \mathbb { R } ^ { n }$ such that $$\left\{ \begin{array} { l } \left( I _ { n } + O \right) x \geq 0 \\ \left( I _ { n } - O \right) x \geq 0 \\ - \left( I _ { n } + { } ^ { t } O \right) z _ { 1 } - \left( I _ { n } - { } ^ { t } O \right) z _ { 2 } \geq 0 \\ z _ { 1 } + \left( I _ { n } + O \right) x > 0 \\ z _ { 2 } + \left( I _ { n } - O \right) x > 0 \\ x - \left( I _ { n } + { } ^ { t } O \right) z _ { 1 } - \left( I _ { n } - { } ^ { t } O \right) z _ { 2 } > 0 \end{array} \right.$$

Let $M \in M_n(\mathbb{Z})$ with nonzero determinant. Show that there exists a matrix $A$ in $\mathrm{GL}_n(\mathbb{Z})$ such that $AM$ is lower triangular and, denoting $AM = (c_{ij})$, we have the inequality $0 \leqslant c_{ij} < c_{jj}$ for all $i, j \in \{1, \ldots, n\}$ such that $j < i$.

Show that $\left\| z _ { 1 } - z _ { 2 } \right\| = \left\| z _ { 1 } + z _ { 2 } \right\|$ and that $- \left( I _ { n } + { } ^ { t } O \right) z _ { 1 } - \left( I _ { n } - { } ^ { t } O \right) z _ { 2 } = 0$.

Deduce from question 6 that $x > 0$ and $x + O x \geq 0$ as well as $x - O x \geq 0$. Conclude.

Show that if $M \in M _ { n } ( \mathbb { R } )$ is antisymmetric (that is ${ } ^ { t } M = -M$) then $I _ { n } + M$ is an invertible matrix.

Show that if $M \in M _ { n } ( \mathbb { R } )$ is antisymmetric, the matrix $$O = \left( I _ { n } + M \right) ^ { - 1 } \left( I _ { n } - M \right)$$ is orthogonal.

Deduce from Broyden's theorem that there exist a strictly positive vector $x$ and a sign diagonal matrix $S$ such that $O x = S x$ and deduce that $u = x + S x$ is the positive vector of Tucker's theorem.

We prove Broyden's theorem by induction on the dimension. We assume $| \alpha | < 1$ and we introduce the matrices $$Q _ { - } = P - \frac { r { } ^ { t } q } { \alpha - 1 } , \quad Q _ { + } = P - \frac { r { } ^ { t } q } { \alpha + 1 }$$ where $O = \left( \begin{array} { l l } P & r \\ { } ^ { t } q & \alpha \end{array} \right)$ with $P \in M _ { n - 1 } ( \mathbb { R } )$, $r , q \in \mathbb { R } ^ { n - 1 }$, $\alpha \in \mathbb { R }$.
Show that the matrices $Q _ { + }$ and $Q _ { - }$ are orthogonal.

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 $\mathcal{S}_{n}(\mathbb{R})$ and $\mathcal{A}_{n}(\mathbb{R})$ are two supplementary orthogonal vector subspaces in $\mathcal{M}_{n}(\mathbb{R})$ and specify their dimensions. (The inner product on $\mathcal{M}_{n}(\mathbb{R})$ is given by $(M,N) \mapsto \operatorname{tr}(M^{\top}N)$.)

Let $A \in \mathcal{M}_{n}(\mathbb{R})$. Show that for every matrix $S \in \mathcal{S}_{n}(\mathbb{R})$, $\|A - A_{s}\|_{2} \leqslant \|A - S\|_{2}$. Specify under what condition on $S \in \mathcal{S}_{n}(\mathbb{R})$ this inequality is an equality.

If $M \in \mathcal{M}_{n}(\mathbb{R})$ and $X, Y \in \mathcal{M}_{n,1}(\mathbb{R})$, the matrix $X^{\top}MY$ belongs to $\mathcal{M}_{1}(\mathbb{R})$ and we agree to identify it with the real number equal to its unique entry.
With this convention, show that $A_{s} \in \mathcal{S}_{n}^{+}(\mathbb{R})$ if and only if $\forall X \in \mathcal{M}_{n,1}(\mathbb{R}), X^{\top}A_{s}X \geqslant 0$ and that $A_{s} \in \mathcal{S}_{n}^{++}(\mathbb{R})$ if and only if $\forall X \in \mathcal{M}_{n,1}(\mathbb{R}) \setminus \{0\}, X^{\top}A_{s}X > 0$.

We consider $A \in \mathcal{M}_{n}(\mathbb{R})$. For every real eigenvalue $\lambda$ of $A$, show that $\min \operatorname{sp}_{\mathbb{R}}(A_{s}) \leqslant \lambda \leqslant \max \operatorname{sp}_{\mathbb{R}}(A_{s})$.
Deduce that if $A_{s} \in \mathcal{S}_{n}^{++}(\mathbb{R})$ then $A$ is invertible.

We consider $A \in \mathcal{M}_{n}(\mathbb{R})$ and assume that $A_{s} \in \mathcal{S}_{n}^{++}(\mathbb{R})$.
a) Show that there exists a unique matrix $B$ in $\mathcal{S}_{n}^{++}(\mathbb{R})$ such that $B^{2} = A_{s}$.
b) Show that there exists a matrix $Q$ in $\mathcal{A}_{n}(\mathbb{R})$ such that $\operatorname{det}(A) = \operatorname{det}(A_{s})\operatorname{det}(I_{n} + Q)$.
c) Deduce that $\operatorname{det}(A) \geqslant \operatorname{det}(A_{s})$.