The difference operator is the endomorphism $\delta$ of $\mathbb{R}_n[X]$ such that $\delta = \tau - \operatorname{Id}_{\mathbb{R}_n[X]}$: $$\delta : \left\{ \begin{array}{l} \mathbb{R}_n[X] \rightarrow \mathbb{R}_n[X] \\ P(X) \mapsto P(X+1) - P(X) \end{array} \right.$$ In this question, we propose to show that there does not exist a linear application $u : \mathbb{R}_n[X] \rightarrow \mathbb{R}_n[X]$ such that $u \circ u = \delta$. We suppose, by contradiction, that such an application $u$ exists.
a) Show that $u$ and $\delta^2$ commute.
b) Deduce that $\mathbb{R}_1[X]$ is stable under the application $u$.
c) Show that there does not exist a matrix $A \in \mathcal{M}_2(\mathbb{R})$ such that $$A^2 = \left(\begin{array}{ll} 0 & 1 \\ 0 & 0 \end{array}\right)$$
d) Conclude.

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 $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.

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.$$

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$.

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.

We prove Broyden's theorem by induction on the dimension. We assume the result holds up to rank $n - 1$ and we write $O$ in the form of a block matrix $$O = \left( \begin{array} { l l } P & r \\ { } ^ { t } q & \alpha \end{array} \right)$$ where $P \in M _ { n - 1 } ( \mathbb { R } )$ and thus $r , q \in \mathbb { R } ^ { n - 1 }$ and $\alpha \in \mathbb { R }$.
Show that $| \alpha | \leq 1$ with equality if and only if $q = r = 0$.

Two simplexes $\mathcal{S}$ and $\mathcal{S}'$ in $\mathbb{R}^n$ are called equivalent if there exist an enumeration of the vertices $s_0, s_1, \ldots, s_n$ of $\mathcal{S}$, and $s_0', s_1', \ldots, s_n'$ of $\mathcal{S}'$, and a matrix $A$ in $\mathrm{GL}_n(\mathbb{Z})$ such that $A(s_i - s_0) = s_i' - s_0'$ for all $i = 1, \ldots, n$.
Show that an integer simplex $\mathcal{S}$ is equivalent to an integer simplex contained in the cube $[0, n!\operatorname{Vol}(\mathcal{S})]^n$.
One may use question 6 for a suitably chosen matrix $M$.

Let $(\Omega, \mathscr{A}, \mathbf{P})$ be a probability space and $X : \Omega \rightarrow \{1, \ldots, N\}$ a random variable with distribution $q \in \Sigma_{N}$. Let $M \in \mathscr{M}_{N,d}(\mathbb{R})$ defined by $M_{i,j} = g_{j}(i)$ for $(i,j) \in \{1, \ldots, N\} \times \{1, \ldots, d\}$, $p \in \Sigma_{N}$ and $m \in \mathbb{R}^{d}$. We denote by $A \in \mathscr{M}_{d}(\mathbb{R})$ the square matrix of size $d \times d$ defined for all $(k,l) \in \{1, \ldots, d\}^{2}$ by $$A_{lk} = \sum_{i=1}^{N} p_{i}(M_{il} - m_{l})(M_{ik} - m_{k}).$$
Verify that if $Y : \Omega \rightarrow \{1, \ldots, N\}$ is a random variable with distribution $p$, then $A_{lk} = \mathbf{E}((g_{l}(Y) - m_{l})(g_{k}(Y) - m_{k}))$ and then that $A$ is a symmetric matrix such that $\theta^{T} A \theta \geqslant 0$ for all $\theta \in \mathbb{R}^{d}$.

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 ${ } ^ { t } P P + q { } ^ { t } q = I _ { n - 1 }$, ${ } ^ { t } P r + \alpha q = 0$ and ${ } ^ { t } r r + \alpha ^ { 2 } = 1$.

Let $M \in \mathscr{M}_{N,d}(\mathbb{R})$ defined by $M_{i,j} = g_{j}(i)$, $p \in \Sigma_{N}$, $m \in \mathbb{R}^{d}$, and $A \in \mathscr{M}_{d}(\mathbb{R})$ defined by $A_{lk} = \sum_{i=1}^{N} p_{i}(M_{il} - m_{l})(M_{ik} - m_{k})$. We denote by $\widetilde{M} = (M \mid \mathbf{1}) \in \mathscr{M}_{N,d+1}(\mathbb{R})$ the augmented matrix obtained by adding a column of 1s to the right of $M$.
Let $\theta \in \mathbb{R}^{d}$ such that $\theta^{T} A \theta = 0$. We assume that $p_{i} \neq 0$ for all $1 \leqslant i \leqslant N$.
(a) Show that there exists $c \in \mathbb{R}$, which you will specify, such that for all $i \in \{1, \ldots, N\}$, we have $\sum_{l=1}^{d} M_{il} \theta_{l} = c$.
(b) Show that if $\ker \widetilde{M} = \{0\}$ then $\theta = 0$.

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 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 $${ } ^ { t } Q _ { + } Q _ { - } = I _ { n - 1 } - \frac { 2 } { 1 - \alpha ^ { 2 } } q { } ^ { t } q$$ and deduce that $$Q _ { - } = Q _ { + } - \frac { 2 } { 1 - \alpha ^ { 2 } } Q _ { + } q { } ^ { t } q$$

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 }$$ Using the induction hypothesis for $Q _ { + }$ (resp. for $Q _ { - }$), we denote by $x _ { + } > 0$ (resp. $x _ { - } > 0$) a vector of $\mathbb { R } ^ { n - 1 }$ and $S _ { + }$ (resp. $S _ { - }$) the sign diagonal matrix, such that $$Q _ { + } x _ { + } = S _ { + } x _ { + } , \quad \text { resp. } \quad Q _ { - } x _ { - } = S _ { - } x _ { - }$$
Show that $$\left( S _ { + } x _ { + } \mid S _ { - } x _ { - } \right) = \left( x _ { + } \mid x _ { - } \right) - \frac { 2 } { 1 - \alpha ^ { 2 } } \left( x _ { + } \mid q \right) \left( x _ { - } \mid q \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 $\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})$.

We consider $A \in \mathcal{M}_{n}(\mathbb{R})$. We assume $A$ is invertible and, in accordance with the notations of the problem, $(A^{-1})_{s}$ denotes the symmetric part of the inverse of $A$. Show that $(\operatorname{det}(A))^{2}\operatorname{det}\left((A^{-1})_{s}\right) = \operatorname{det}(A_{s})$.
One may consider $A(A^{-1})_{s}A^{\top}$.

Let $A \in \mathrm{O}_{n}(\mathbb{R})$. Show that the eigenvalues of $A_{s}$ are in $[-1,1]$.