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

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 if $M \in M _ { n } ( \mathbb { R } )$ is antisymmetric (that is ${ } ^ { t } M = -M$) then $I _ { n } + M$ is an invertible matrix.

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

We denote $E_{n} = \mathcal{M}_{n,1}(\mathbb{R})$ equipped with the inner product $(X \mid Y) = X^{\top}Y$. A matrix in $\mathcal{M}_{n}(\mathbb{R})$ is called $F$-singular if there exists a non-zero $X \in F$ such that $\forall Z \in F, Z^{\top}KX = 0$.
Show that a matrix in $\mathcal{M}_{n}(\mathbb{R})$ is singular if and only if it is $E_{n}$-singular.

Show that a matrix in $\mathcal{M}_{n}(\mathbb{R})$ is singular if and only if it is $E_{n}$-singular.

Let $n$ and $p$ be two integers greater than or equal to 2. We fix a sequence $\left( A _ { k } \right) _ { k \in \mathbb { N } }$ of matrices of $\mathrm { GL } _ { n } ( \mathbb { C } )$ which is $p$-periodic. The sequence $\left( \Phi _ { k } \right) _ { k \in \mathbb { N } }$ is defined by $\Phi _ { 0 } = I _ { n }$ and $\Phi _ { k + 1 } = A _ { k } \Phi _ { k }$. We denote by $B$ a matrix belonging to $\mathrm { GL } _ { n } ( \mathbb { C } )$ satisfying $B ^ { p } = \Phi _ { p }$. Prove that there exists a unique sequence $\left( P _ { k } \right) _ { k \in \mathbb { N } } \in \left( \mathrm { GL } _ { n } ( \mathbb { C } ) \right) ^ { \mathbb { N } }$, periodic of period $p$, such that $$\forall k \in \mathbb { N } , \quad \Phi _ { k } = P _ { k } B ^ { k }$$

Let $m \geq 2$ be a natural integer and $E$ an $\mathbb{R}$-vector space of dimension $2m+1$. Let $T$ be an endomorphism of $E$ satisfying (H1): $T^{2m} \neq 0_{\mathcal{L}(E)}$ and $T^{2m+1} = 0_{\mathcal{L}(E)}$.
Show that for any real number $\alpha$, the endomorphism $\operatorname{Id}_E + \alpha T^2$ is bijective and that $$\left(\operatorname{Id}_E + \alpha T^2\right)^{-1} = \sum_{k=0}^{m} (-1)^k \alpha^k T^{2k}$$ where $\left(\operatorname{Id}_E + \alpha T^2\right)^{-1}$ denotes the inverse endomorphism of $\operatorname{Id}_E + \alpha T^2$.

Let $\tau$ be a strictly positive real and $q$ a natural integer greater than or equal to 2. We set $\delta = \frac{1}{q+1}$ and $r = \frac{\tau}{\delta^{2}}$. The numerical scheme imposes, for any natural integer $n$ and any $k \in \llbracket 1, q \rrbracket$: $$\frac{f_{n+1}(k) - f_{n}(k)}{\tau} = \frac{f_{n}(k+1) - 2f_{n}(k) + f_{n}(k-1)}{\delta^{2}}$$ as well as $f_{n}(0) = f_{n}(q+1) = 0$. We set $F_{n} = \left(\begin{array}{c} f_{n}(1) \\ \vdots \\ f_{n}(q) \end{array}\right)$, $I_{q}$ is the identity matrix of order $q$, $B$ is the square matrix of order $q$ with coefficient $(i,j)$ equal to 1 if $|i-j|=1$ and 0 otherwise, and $A = (1-2r)I_{q} + rB$. Show that, for all $n \in \mathbb{N}$, $F_{n+1} = A F_{n}$.

We consider the family of matrices $B = \left[ b _ { i , j } \right] _ { 1 \leq i , j \leq n } \in \mathcal { M } _ { n } ( \mathbb { R } )$ satisfying the following three properties (called $M$-matrices):
$$\forall i \in \{ 1 , \ldots , n \} , \left\{ \begin{array} { l } b _ { i , i } > 0 \\ b _ { i , j } \leq 0 \text { for all } j \neq i \\ \sum _ { j = 1 } ^ { n } b _ { i , j } > 0 \end{array} \right.$$
Show that if $B$ is an $M$-matrix, then we have
(a) $B$ is invertible
(b) If $F = {}^{ t } \left( f _ { 1 } , \ldots , f _ { n } \right)$ has all positive coordinates, then $B ^ { - 1 } F$ also,
(c) all coefficients of $B ^ { - 1 }$ are positive.

By applying the previous results to $A _ { n } + \varepsilon I _ { n }$ with $\varepsilon > 0$, show that all coefficients of $A _ { n } ^ { - 1 }$ are positive.

Let $n \in \mathbb{N}^*$, $h = \frac{1}{n+1}$, and $x_i = ih$ for all $i \in \{0, \ldots, n+1\}$. Show that there exists a unique family of real numbers $\left( u _ { i } \right) _ { 0 \leq i \leq n + 1 }$ satisfying
$$\left\{ \begin{array} { l } - \frac { 1 } { h ^ { 2 } } \left( u _ { i + 1 } + u _ { i - 1 } - 2 u _ { i } \right) + c \left( x _ { i } \right) u _ { i } = f \left( x _ { i } \right) , \text { for } 1 \leq i \leq n \\ u _ { 0 } = u _ { n + 1 } = 0 \end{array} \right.$$

Show that if $f$ is positive, then $u _ { i } \geq 0$ for all $i \in \{ 0 , \ldots , n + 1 \}$.

Let $C$ be a nilpotent matrix. Show that $I_n + C$ is invertible and that $$\left(I_n + C\right)^{-1} = I_n - C + C^2 + \cdots + (-1)^{n-1} C^{n-1}$$

Let $p , k$ be two strictly positive integers and $V \in \mathscr { M } _ { p , k } ( \mathbb { R } )$ such that $V ^ { \mathrm { T } } V = I _ { k }$. For all $W \in \mathscr { M } _ { p , k } ( \mathbb { R } )$, we denote by $M _ { V , W }$ the matrix of $\mathscr { M } _ { p + k } ( \mathbb { R } )$ defined in blocks by $$M _ { V , W } = \left( \begin{array} { c c } V & I _ { p } \\ O _ { k } & W ^ { \mathrm { T } } \end{array} \right) .$$
We assume here that $W ^ { \mathrm { T } } V$ is an invertible matrix.
(a) Show that $M _ { V , W }$ is invertible. We denote its inverse by $M _ { V , W } ^ { - 1 }$.
(b) Show that the orthogonal complement $\operatorname { Im } ( W ) ^ { \perp }$ of $\operatorname { Im } ( W )$ and $\operatorname { Im } ( V )$ are two supplementary subspaces in $\mathbb { R } ^ { p }$, i.e., $\operatorname { Im } ( W ) ^ { \perp } \oplus \operatorname { Im } ( V ) = \mathbb { R } ^ { p }$. Hint: You may start by verifying that for $z \in \mathbb { R } ^ { p }$, if $z \in \operatorname { Im } ( W ) ^ { \perp }$ then $W ^ { \mathrm { T } } z = 0$.
(c) We define the matrix $$P _ { V , W } = \left( \begin{array} { l l } V & O _ { p } \end{array} \right) M _ { V , W } ^ { - 1 } \binom { I _ { p } } { O _ { k , p } } .$$ Show that $P _ { V , W }$ is the matrix of the projection onto $\operatorname { Im } ( V )$ parallel to $\operatorname { Im } ( W ) ^ { \perp }$.

Let $q \in \mathbb { N } ^ { * }$. Show that the set of invertible matrices of $\mathscr { M } _ { q } ( \mathbb { R } )$ is an open set and that the map $M \mapsto M ^ { - 1 }$ is continuous on this open set.

Let $A$ denote a matrix in $\mathcal{M}_n(\mathbb{C})$. Assume that $P$ is an annihilating polynomial of $A$ nilpotent.
We denote by $m$ the multiplicity of 0 in $P$, which allows us to write $P = X^m Q$ where $Q$ is a polynomial in $\mathbb{C}[X]$ such that $Q(0) \neq 0$. Prove that $Q(A)$ is invertible and then that $P$ is a multiple of $X^p$ in $\mathbb{C}[X]$.

Let $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$. We are given $b \in \mathbb { R } ^ { N }$ and we denote by $\tilde { x } \in \mathbb { R } ^ { N }$ the unique vector satisfying $A \tilde { x } = b$. We are given a vector $x _ { 0 } \in \mathbb { R } ^ { N }$, different from $\tilde { x }$, and we denote by $r _ { 0 } = b - A x _ { 0 }$. We set $H _ { 0 } = \{ 0 \}$ and for $k \geq 1$, $$H _ { k } = \left\{ P ( A ) r _ { 0 } \mid P \in \mathbb { R } [ X ] , \operatorname { deg } ( P ) \leq k - 1 \right\}$$ where $\operatorname { deg } ( P ) \in \mathbb { N }$ denotes the degree of the polynomial $P$.
Show that the $H _ { k }$ form a sequence of vector subspaces of $\mathbb { R } ^ { N }$, and show that $H _ { k } \subset H _ { k + 1 }$ for all $k \in \mathbb { N }$.
a) Show that there necessarily exists $k$ such that $H _ { k + 1 } = H _ { k }$. We then denote by $m$ the smallest integer $k$ such that $H _ { k + 1 } = H _ { k }$.
b) Show that $\operatorname { dim } \left( H _ { k } \right) = m$ for all $k \geq m$, and that $\operatorname { dim } \left( H _ { k } \right) = k$ for $k \leq m$.

Let $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$. We are given $b \in \mathbb { R } ^ { N }$ and we denote by $\tilde { x } \in \mathbb { R } ^ { N }$ the unique vector satisfying $A \tilde { x } = b$. We are given a vector $x _ { 0 } \in \mathbb { R } ^ { N }$, different from $\tilde { x }$, and we denote by $r _ { 0 } = b - A x _ { 0 }$. We set $H _ { 0 } = \{ 0 \}$ and for $k \geq 1$, $$H _ { k } = \left\{ P ( A ) r _ { 0 } \mid P \in \mathbb { R } [ X ] , \operatorname { deg } ( P ) \leq k - 1 \right\}$$ We denote by $m$ the smallest integer $k$ such that $H _ { k + 1 } = H _ { k }$. We define $x _ { 0 } + H _ { k }$ as the subset of points of $\mathbb { R } ^ { N }$ of the form $x _ { 0 } + x$ where $x$ ranges over the vector space $H _ { k }$.
a) Show that $\tilde { x } \in x _ { 0 } + H _ { m }$.
b) Show that, for all $k \in \{ 0 , \ldots , m - 1 \}$, we have $\tilde { x } \notin x _ { 0 } + H _ { k }$.

We introduce the map $$\begin{aligned} J : \mathbb { R } ^ { N } & \rightarrow \mathbb { R } \\ x & \mapsto \frac { 1 } { 2 } \langle x , A x \rangle - \langle b , x \rangle \end{aligned}$$ where $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$, $b \in \mathbb { R } ^ { N }$, and $\tilde { x }$ is the unique vector satisfying $A \tilde { x } = b$.
For all $x \in \mathbb { R } ^ { N }$, express $\| x - \tilde { x } \| _ { A } ^ { 2 } = \langle x - \tilde { x } , A ( x - \tilde { x } ) \rangle$ in terms of $J ( \tilde { x } )$ and $J ( x )$ and deduce that $\tilde { x }$ is the unique minimizer of $J$ on $\mathbb { R } ^ { N }$, that is, $J ( \tilde { x } ) \leq J ( x )$ for all $x \in \mathbb { R } ^ { N }$, and that $\tilde { x }$ is the only point satisfying this property.

We introduce the map $$\begin{aligned} J : \mathbb { R } ^ { N } & \rightarrow \mathbb { R } \\ x & \mapsto \frac { 1 } { 2 } \langle x , A x \rangle - \langle b , x \rangle \end{aligned}$$ where $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$, $b \in \mathbb { R } ^ { N }$. We set $H _ { 0 } = \{ 0 \}$ and for $k \geq 1$, $$H _ { k } = \left\{ P ( A ) r _ { 0 } \mid P \in \mathbb { R } [ X ] , \operatorname { deg } ( P ) \leq k - 1 \right\}$$ and $x _ { 0 } + H _ { k }$ denotes the subset of points of $\mathbb { R } ^ { N }$ of the form $x _ { 0 } + x$ where $x$ ranges over $H _ { k }$.
Show that $J$ admits a unique minimizer on the subset $x _ { 0 } + H _ { k }$, for any $k \in \mathbb { N }$.

We fix two $p$-tuples $(x_i)_{i \in \llbracket 1,p \rrbracket}$ and $(a_i)_{i \in \llbracket 1,p \rrbracket}$ of real numbers. We assume that the $x_i$ are pairwise distinct. We denote $\mathcal{S} = \{h \in \mathcal{H} \mid h(x_i) = a_i\}$ the set of $h \in \mathcal{H}$ that equal $a_i$ at $x_i$ for all $i \in \llbracket 1,p \rrbracket$. We denote $J : \mathcal{H} \rightarrow \mathbf{R}$ defined by $J(h) = \frac{1}{2}\|h\|_{\mathcal{H}}^2$ and $J_* = \inf\{J(h) \mid h \in \mathcal{S}\}$. We denote $\mathcal{S}_* = \{h \in \mathcal{S} \mid J(h) = J_*\}$.
Show that $\mathcal{S}_*$ has at most one element.

We fix two $p$-tuples $(x_i)_{i \in \llbracket 1,p \rrbracket}$ and $(a_i)_{i \in \llbracket 1,p \rrbracket}$ of real numbers with the $x_i$ pairwise distinct. Let $\alpha \in \mathbf{R}^p$ (resp. $a \in \mathbf{R}^p$) be the vector with coordinates $(\alpha_i)_{i \in \llbracket 1,p \rrbracket}$ (resp. $(a_i)_{i \in \llbracket 1,p \rrbracket}$) and $h_\alpha = \sum_{i=1}^p \alpha_i \tau_{x_i}(\gamma_{2\lambda})$. The matrix $K$ is defined by $K_{ij} = \exp\left(-\frac{|x_i - x_j|^2}{2\lambda}\right)$ (here in the case $d=1$).
(a) Show that $h_\alpha$ is an interpolant if and only if $K\alpha = a$ where $K$ is the matrix introduced in question (6) (here in the case $d = 1$).
(b) Show that $K$ is invertible.

We fix two $p$-tuples $(x_i)_{i \in \llbracket 1,p \rrbracket}$ and $(a_i)_{i \in \llbracket 1,p \rrbracket}$ of real numbers with the $x_i$ pairwise distinct. We use the notation $\alpha_*$, $h_\alpha$, $K$, $a$, $\mathcal{S}_*$, $J_*$, $(\mid)_{\mathcal{H}}$ as defined previously.
Deduce that there exists $\alpha_* \in \mathbf{R}^p$ such that $\mathcal{S}_* = \{h_{\alpha_*}\}$ and calculate the value of $J_*$ in terms of $K$ and $a$.

Let $M \in M _ { n } ( \mathbb { R } )$, all of whose coefficients are non-negative. Show that $M$ is a stochastic matrix if and only if $$M \left( \begin{array} { c } 1 \\ \vdots \\ 1 \end{array} \right) = \left( \begin{array} { c } 1 \\ \vdots \\ 1 \end{array} \right) .$$