Show that the transition matrix of a graph (defined in part I) is a stochastic matrix and that, for every natural integer $k$, the vector $P ^ { ( k ) }$, also defined in part I, is a probability distribution.

Let $M \in \mathcal{M}_{k \times d}(\mathbb{R})$ with $\operatorname{rank}(M) = k$, $b \in \mathbb{R}^k \backslash \{0\}$, and fix $\bar{x} \in C$ where $C := \{x \in \mathbb{R}^d : Mx = b, \|x\|_1 = r\}$. Let $q \in \operatorname{Ker}(M)^\perp \backslash \{0\}$ be as in question 23. Let $K$ be the set of $y \in \mathbb{R}^d$ such that $$My = b, \quad y_i = 0 \ \forall i \in I_0(\bar{x}), \quad q_i y_i \geqslant 0 \ \forall i \in \{1, \ldots, d\}$$ Show that $K$ is non-empty and included in $C$.

Let $M \in \mathcal{M}_{k \times d}(\mathbb{R})$ with $\operatorname{rank}(M) = k$, $b \in \mathbb{R}^k \setminus \{0\}$, $\bar{x} \in C$ (where $C := \{x \in \mathbb{R}^d : Mx = b, \|x\|_1 = r\}$), and $q \in \operatorname{Ker}(M)^\perp \setminus \{0\}$ as in question 23. Let $K$ be the set of $y \in \mathbb{R}^d$ such that $$My = b, \quad y_i = 0 \quad \forall i \in I_0(\bar{x}), \quad q_i y_i \geq 0 \quad \forall i \in \{1, \ldots, d\}.$$ Show that $K$ is non-empty and included in $C$.

Let $A \in S_n^{++}(\mathbf{R})$ and $M \in S_n(\mathbf{R})$. Let $\varepsilon_0 > 0$ be such that for all $t \in ]-\varepsilon_0, \varepsilon_0[, A + tM \in S_n^{++}(\mathrm{R})$. We admit that the function $\Phi : t \mapsto (A + tM)^{-1}$ is of class $C^1$ on $]-\varepsilon_0, \varepsilon_0[$. By noting that $\Phi(t) \times (A + tM) = I_n$, show that $$\Phi(t) \underset{t \rightarrow 0}{=} A^{-1} - A^{-1}MA^{-1} t + o(t).$$

Let $A \in S _ { n } ^ { + + } ( \mathbf { R } )$ and $M \in S _ { n } ( \mathbf { R } )$, and let $\varepsilon_0 > 0$ be such that for all $t \in ] - \varepsilon _ { 0 } , \varepsilon _ { 0 } [ , A + t M \in S _ { n } ^ { + + } ( \mathbf { R } )$. We admit that the function $\Phi : t \mapsto ( A + t M ) ^ { - 1 }$ is of class $C ^ { 1 }$ on $] - \varepsilon _ { 0 } , \varepsilon _ { 0 } [$. By noting that $\Phi ( t ) \times ( A + t M ) = I _ { n }$, show that
$$\Phi ( t ) \underset { t \rightarrow 0 } { = } A ^ { - 1 } - A ^ { - 1 } M A ^ { - 1 } t + o ( t )$$

Consider an open set $U \subset \mathbb{R}^n$, $h : U \rightarrow \mathbb{R}$ a $\mathcal{C}^1$ application and $b \in \mathbb{R}^m$. Assume that there exists $x_* \in U$ a minimum of $h$ on the set $V_b = \{x \in U \mid Ax + b = 0\}$.
(a) Show that for all $u \in \mathbb{R}^n$ such that $Au = 0$ we have $\left\langle \nabla h(x_*), u \right\rangle_{\mathbb{R}^n} = 0$ where $\nabla h(x)$ denotes the gradient of $h$ at $x$.
(b) Show the existence of $\nu_* \in \mathbb{R}^m$ such that $\nabla h(x_*) - A^T \nu_* = 0$.
(c) Deduce that the application $L : U \times \mathbb{R}^m \rightarrow \mathbb{R}$ such that $L(x, \nu) = h(x) - \langle \nu, Ax + b \rangle_{\mathbb{R}^m}$ satisfies $\frac{\partial L}{\partial x_k}(x_*, \nu_*) = 0$ for all $1 \leq k \leq n$ where $\frac{\partial L}{\partial x_k}(x, \nu)$ denotes the partial derivative of $L$ with respect to the $k$-th coordinate of $x \in \mathbb{R}^n$.
(d) Conclude that if $U$ is convex, and $h$ is convex on $U$, then $L$ admits a saddle point at $(x_*, \nu_*)$, that is, we have $$L(x_*, \nu) \leq L(x_*, \nu_*) \leq L(x, \nu_*)$$ for all $(x, \nu) \in U \times \mathbb{R}^m$.

We consider $M \in \mathscr { D } _ { \rho } \left( S _ { n } ( \mathbb { R } ) \right)$. We fix a real eigenvalue $\lambda$ of $M _ { \mid t = 0 }$ and denote by $d$ its multiplicity as a root of $\chi _ { \mid t = 0 }$ where $\chi = \det(XI_n - M)$. We set $A = F ( M )$ and $B = G ( M )$, and $Q = ( B U \mid A V ) \in \mathscr { D } _ { \rho _ { 1 } } \left( \mathscr { M } _ { n } ( \mathbb { R } ) \right)$ where $U \in \mathscr { M } _ { n , d } ( \mathbb { R } )$ and $V \in \mathscr { M } _ { n , n - d } ( \mathbb { R } )$ are as in question 20.
Show that there exists $\rho _ { 2 } \in \mathbb { R } _ { + } ^ { * }$, $\rho _ { 2 } \leqslant \rho _ { 1 }$ such that $Q \in \operatorname { GL } _ { n } \left( \mathscr { D } _ { \rho _ { 2 } } ( \mathbb { R } ) \right)$. (One may use the result of question 6.)

Let $m \in \mathbb{N}$. We consider the matrix $$M = \left(\begin{array}{cccccc} \binom{0}{0} & 0 & \cdots & \cdots & \cdots & 0 \\ \binom{1}{0} & \binom{1}{1} & 0 & & & \vdots \\ \vdots & & \ddots & \ddots & & \vdots \\ \vdots & & & \ddots & \ddots & \vdots \\ \binom{m-1}{0} & & & & \binom{m-1}{m-1} & 0 \\ \binom{m}{0} & \cdots & \cdots & \cdots & \cdots & \binom{m}{m} \end{array}\right) \in \mathscr{M}_{m+1}(\mathbb{R}).$$ Establish that $M$ is invertible and explicitly determine its inverse.

Let $m \in \mathbb{N}$. We consider the matrix $$M = \left(\begin{array}{cccccc} \binom{0}{0} & 0 & \cdots & \cdots & \cdots & 0 \\ \binom{1}{0} & \binom{1}{1} & 0 & & & \vdots \\ \vdots & & \ddots & \ddots & & \vdots \\ \vdots & & & \ddots & \ddots & \vdots \\ \binom{m-1}{0} & & & & \binom{m-1}{m-1} & 0 \\ \binom{m}{0} & \cdots & \cdots & \cdots & \cdots & \binom{m}{m} \end{array}\right) \in \mathscr{M}_{m+1}(\mathbb{R}).$$ Establish that $M$ is invertible and explicitly determine its inverse.

For every $\lambda \in \mathbb{C}$ nonzero, we set $J_n(\lambda) = \lambda I_n + N$, where $N = (n_{i,j})_{1 \leq i,j \leq n}$ with $n_{i,j} = 1$ if $j = i+1$ and $n_{i,j} = 0$ otherwise.
Prove that $J_n(\lambda)$ is invertible and determine in terms of $N$ and $\lambda$ the matrix $N'$ such that $J_n(\lambda)^{-1} = \frac{1}{\lambda} I_n + N'$.

For every $\lambda \in \mathbf{C}$ nonzero, we set $J_n(\lambda) = \lambda I_n + N$. Prove that $J_n(\lambda)$ is invertible and determine in terms of $N$ and $\lambda$ the matrix $N'$ such that $J_n(\lambda)^{-1} = \frac{1}{\lambda} I_n + N'$.

Show that $V A = B$ where $V \in \mathcal { M } _ { N } ( \mathbf { R } )$ is a matrix that you will make explicit.
Here $A = \left( a_1, a_2, \ldots, a_N \right)^\top \in \mathbf{R}^N$, $B = \left( \beta_0, \beta_1, \ldots, \beta_{N-1} \right)^\top \in \mathbf{R}^N$, and $\beta_k = \sum_{n=1}^{N} \lambda_n^k a_n$.

Prove that the system $V A = B$ admits a unique solution $A \in \mathbf { R } ^ { N }$.
Here $V$ is the matrix from question 14, with entries $V_{k,n} = \lambda_n^{k-1}$ for $k = 1,\ldots,N$ and $n = 1,\ldots,N$, and the $\lambda_n$ are strictly increasing real numbers.

Let $A \in \mathrm{GL}_n(\mathbb{R})$ be an invertible matrix, and let $\mathbf{u}, \mathbf{v} \in \mathbb{R}^n$. Show that $A + \mathbf{u v}^T$ is invertible if and only if $\left\langle \mathbf{v}, A^{-1}\mathbf{u} \right\rangle \neq -1$.

Let $A \in \mathrm{GL}_n(\mathbb{R})$ be an invertible matrix, and let $\mathbf{u}, \mathbf{v} \in \mathbb{R}^n$. Suppose that $A + \mathbf{u v}^T$ is invertible. Show that $$\left(A + \mathbf{u v}^T\right)^{-1} = A^{-1} - \frac{A^{-1}\mathbf{u}\mathbf{v}^T A^{-1}}{1 + \left\langle \mathbf{v}, A^{-1}\mathbf{u} \right\rangle}$$

As in the third part, we suppose that $B = A + \mathbf{u}\mathbf{u}^T$ with $A \in \mathcal{S}_n(\mathbb{R})$ a symmetric matrix, and $\mathbf{u} \in \mathbb{R}^n$ a vector such that $\|\mathbf{u}\| = 1$. We denote by $\lambda_1 \leqslant \lambda_2 \leqslant \cdots \leqslant \lambda_n$ the eigenvalues of $A$ and $\mu_1 \leqslant \mu_2 \leqslant \cdots \leqslant \mu_n$ those of $B$. We admit that $$\lambda_1 \leqslant \mu_1 \leqslant \lambda_2 \leqslant \mu_2 \leqslant \cdots \leqslant \lambda_n \leqslant \mu_n.$$ We further suppose that there exists an integer $m \in \{1, 2, \ldots, n-1\}$ such that the eigenvalues of $A$ satisfy $$0 = \lambda_1 = \lambda_2 = \cdots = \lambda_m < \lambda_{m+1} \leqslant \cdots \leqslant \lambda_n.$$ Let $\varepsilon \in ]0, \lambda_{m+1}[$.
Justify that $(A - \varepsilon \mathbb{I}_n)$ is invertible.

As in the third part, we suppose that $B = A + \mathbf{u}\mathbf{u}^T$ with $A \in \mathcal{S}_n(\mathbb{R})$ a symmetric matrix, and $\mathbf{u} \in \mathbb{R}^n$ a vector such that $\|\mathbf{u}\| = 1$. We denote by $\lambda_1 \leqslant \lambda_2 \leqslant \cdots \leqslant \lambda_n$ the eigenvalues of $A$ and $\mu_1 \leqslant \mu_2 \leqslant \cdots \leqslant \mu_n$ those of $B$. We admit that $$\lambda_1 \leqslant \mu_1 \leqslant \lambda_2 \leqslant \mu_2 \leqslant \cdots \leqslant \lambda_n \leqslant \mu_n.$$ We further suppose that there exists an integer $m \in \{1, 2, \ldots, n-1\}$ such that the eigenvalues of $A$ satisfy $$0 = \lambda_1 = \lambda_2 = \cdots = \lambda_m < \lambda_{m+1} \leqslant \cdots \leqslant \lambda_n.$$ Let $\varepsilon \in ]0, \lambda_{m+1}[$. We suppose that $\left\langle \mathbf{u}, \left(A - \varepsilon \mathbb{I}_n\right)^{-1}\mathbf{u}\right\rangle < -1$.
Show that $(B - \varepsilon \mathbb{I}_n)$ is invertible.

As in the third part, we suppose that $B = A + \mathbf{u}\mathbf{u}^T$ with $A \in \mathcal{S}_n(\mathbb{R})$ a symmetric matrix, and $\mathbf{u} \in \mathbb{R}^n$ a vector such that $\|\mathbf{u}\| = 1$. We denote by $\lambda_1 \leqslant \lambda_2 \leqslant \cdots \leqslant \lambda_n$ the eigenvalues of $A$ and $\mu_1 \leqslant \mu_2 \leqslant \cdots \leqslant \mu_n$ those of $B$. We admit that $$\lambda_1 \leqslant \mu_1 \leqslant \lambda_2 \leqslant \mu_2 \leqslant \cdots \leqslant \lambda_n \leqslant \mu_n.$$ We further suppose that there exists an integer $m \in \{1, 2, \ldots, n-1\}$ such that the eigenvalues of $A$ satisfy $$0 = \lambda_1 = \lambda_2 = \cdots = \lambda_m < \lambda_{m+1} \leqslant \cdots \leqslant \lambda_n.$$ Let $\varepsilon \in ]0, \lambda_{m+1}[$. We suppose that $\left\langle \mathbf{u}, \left(A - \varepsilon \mathbb{I}_n\right)^{-1}\mathbf{u}\right\rangle < -1$.
Show that $\operatorname{Tr}\left(\left(B - \varepsilon \mathbb{I}_n\right)^{-1}\right) > \operatorname{Tr}\left(\left(A - \varepsilon \mathbb{I}_n\right)^{-1}\right)$.

Let $A \in \mathrm{GL}_n(\mathbb{R})$ be an invertible matrix, and let $\mathbf{u}, \mathbf{v} \in \mathbb{R}^n$. Show that $A + \mathbf{u v}^T$ is invertible if and only if $\left\langle \mathbf{v}, A^{-1} \mathbf{u} \right\rangle \neq -1$.

Let $A \in \mathrm{GL}_n(\mathbb{R})$ be an invertible matrix, and let $\mathbf{u}, \mathbf{v} \in \mathbb{R}^n$. Suppose that $A + \mathbf{u v}^T$ is invertible. Show that $$\left(A + \mathbf{u v}^T\right)^{-1} = A^{-1} - \frac{A^{-1} \mathbf{u v}^T A^{-1}}{1 + \left\langle \mathbf{v}, A^{-1} \mathbf{u} \right\rangle}.$$

As in the third part, we assume that $B = A + \mathbf{u u}^T$ with $A \in \mathcal{S}_n(\mathbb{R})$ a symmetric matrix, and $\mathbf{u} \in \mathbb{R}^n$ a vector such that $\|\mathbf{u}\| = 1$. We denote by $\lambda_1 \leqslant \lambda_2 \leqslant \cdots \leqslant \lambda_n$ the eigenvalues of $A$ and $\mu_1 \leqslant \mu_2 \leqslant \cdots \leqslant \mu_n$ those of $B$. We admit that $$\lambda_1 \leqslant \mu_1 \leqslant \lambda_2 \leqslant \mu_2 \leqslant \cdots \leqslant \lambda_n \leqslant \mu_n.$$ We further assume that there exists an integer $m \in \{1,2,\ldots,n-1\}$ such that the eigenvalues of $A$ satisfy $$0 = \lambda_1 = \lambda_2 = \cdots = \lambda_m < \lambda_{m+1} \leqslant \cdots \leqslant \lambda_n.$$ Let $\varepsilon \in ]0, \lambda_{m+1}[$. Justify that $(A - \varepsilon \mathbb{I}_n)$ is invertible.

As in the third part, we assume that $B = A + \mathbf{u u}^T$ with $A \in \mathcal{S}_n(\mathbb{R})$ a symmetric matrix, and $\mathbf{u} \in \mathbb{R}^n$ a vector such that $\|\mathbf{u}\| = 1$. We denote by $\lambda_1 \leqslant \lambda_2 \leqslant \cdots \leqslant \lambda_n$ the eigenvalues of $A$ and $\mu_1 \leqslant \mu_2 \leqslant \cdots \leqslant \mu_n$ those of $B$. We admit that $$\lambda_1 \leqslant \mu_1 \leqslant \lambda_2 \leqslant \mu_2 \leqslant \cdots \leqslant \lambda_n \leqslant \mu_n.$$ We further assume that there exists an integer $m \in \{1,2,\ldots,n-1\}$ such that the eigenvalues of $A$ satisfy $$0 = \lambda_1 = \lambda_2 = \cdots = \lambda_m < \lambda_{m+1} \leqslant \cdots \leqslant \lambda_n.$$ Let $\varepsilon \in ]0, \lambda_{m+1}[$. We suppose that $\left\langle \mathbf{u}, \left(A - \varepsilon \mathbb{I}_n\right)^{-1} \mathbf{u} \right\rangle < -1$. Show that $(B - \varepsilon \mathbb{I}_n)$ is invertible.

The number of distinct real values of $\lambda$ for which the system of linear equations $$x + y + z = 0$$ $$x + \lambda y + z = 0$$ $$x + y + \lambda z = 0$$ has a non-trivial solution is
(A) 0
(B) 1
(C) 2
(D) 3

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 $A$ in $\mathscr { A }$ for which the system of linear equations
$$A \left[ \begin{array} { l } x \\ y \\ z \end{array} \right] = \left[ \begin{array} { l } 1 \\ 0 \\ 0 \end{array} \right]$$
has a unique solution, is
(A) less than 4
(B) at least 4 but less than 7
(C) at least 7 but less than 10
(D) at least 10

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 $A$ in $\mathscr { A }$ for which the system of linear equations
$$A \left[ \begin{array} { l } x \\ y \\ z \end{array} \right] = \left[ \begin{array} { l } 1 \\ 0 \\ 0 \end{array} \right]$$
is inconsistent, is
(A) 0
(B) more than 2
(C) 2
(D) 1