For every matrix $A$ in $\mathcal{M}_n(\mathbb{K})$, we set $N(A) = \max_{1 \leqslant i \leqslant n}\left(\sum_{j=1}^{n}|a_{i,j}|\right)$. Show that the map $A \mapsto N(A)$ is a sub-multiplicative norm on $\mathcal{M}_n(\mathbb{K})$.

For every matrix $A$ in $\mathcal{M}_n(\mathbb{K})$, we set $N(A) = \max_{1 \leqslant i \leqslant n}\left(\sum_{j=1}^{n}|a_{i,j}|\right)$. Let $Q \in \mathrm{GL}_n(\mathbb{K})$. Show that $A \mapsto \|A\| = N\left(Q^{-1}AQ\right)$ is a sub-multiplicative norm on $\mathcal{M}_n(\mathbb{K})$.

We are given $A$ in $\mathcal{M}_n(\mathbb{C})$, with $\rho(A) < 1$. We want to show that $\lim_{m \rightarrow +\infty} A^m = 0$.
Let $P$ be in $\mathrm{GL}_n(\mathbb{C})$ and let $T$ be upper triangular, such that $A = PTP^{-1}$. We are given $\delta > 0$. We set $\Delta = \operatorname{diag}\left(1, \delta, \ldots, \delta^{n-1}\right)$ and $\widehat{T} = \Delta^{-1}T\Delta$.
Show that $\widehat{T}$ is upper triangular and that we can choose $\delta$ so that $N(\widehat{T}) < 1$.

We are given $A$ in $\mathcal{M}_n(\mathbb{C})$, with $\rho(A) < 1$. Let $P$ be in $\mathrm{GL}_n(\mathbb{C})$ and let $T$ be upper triangular, such that $A = PTP^{-1}$. We are given $\delta > 0$. We set $\Delta = \operatorname{diag}\left(1, \delta, \ldots, \delta^{n-1}\right)$ and $\widehat{T} = \Delta^{-1}T\Delta$.
With the choice of $\delta$ such that $N(\widehat{T}) < 1$, we set $Q = P\Delta$ and we equip $\mathcal{M}_n(\mathbb{C})$ with the norm $M \mapsto \|M\| = N\left(Q^{-1}MQ\right)$.
Show that $\|A\| < 1$ and deduce $\lim_{m \rightarrow +\infty} A^m = 0$.

Let $A$ denote a positive matrix in $\mathcal{M}_n(\mathbb{R})$.
Show that if there exists in $A$ a path from $i$ to $j$, with $i \neq j$, then there exists an elementary path from $i$ to $j$ of length $\ell \leqslant n-1$. Similarly, show that if there exists in $A$ a circuit passing through $i$, then there exists an elementary circuit passing through $i$ of length $\ell \leqslant n$.

Let $A \geqslant 0$ in $\mathcal{M}_n(\mathbb{R})$. Let $i, j$ be in $\llbracket 1, n \rrbracket$. Let $m \geqslant 1$. Show the equivalence of the propositions:

• there exists in $A$ a path with origin $i$, endpoint $j$, of length $m$;
• the entry with indices $i, j$ of $A^m$ (denoted $a_{i,j}^{(m)}$) is strictly positive.

You may proceed by induction on the integer $m \geqslant 1$.

Let $A$ denote a positive matrix in $\mathcal{M}_n(\mathbb{R})$. Let $i, j$ be in $\llbracket 1, n \rrbracket$, and let $\ell$ and $m$ be in $\mathbb{N}^*$. Show the equivalence of the propositions:

• there exists in $A^m$ a path with origin $i$, endpoint $j$, of length $\ell$;
• there exists in $A$ a path with origin $i$, endpoint $j$, of length $m\ell$.

Let $A$ be a primitive matrix in $\mathcal{M}_n(\mathbb{R})$.
Show that for all $i \neq j$ there exists in $A$ an elementary path from $i$ to $j$ of length $\ell \leqslant n-1$, and that for all $i$ there exists in $A$ an elementary circuit passing through $i$ of length $\ell \leqslant n$.

Give a simple example of a square matrix that is primitive but not strictly positive.

Let $B > 0$ in $\mathcal{M}_n(\mathbb{R})$ and $x \geqslant 0$ in $\mathbb{R}^n$ with $x \neq 0$. Show that $Bx > 0$.

Let $A$ be a primitive matrix and $m \in \mathbb{N}^*$ such that $A^m > 0$. Show that $\forall p \geqslant m, A^p > 0$. You may note, by justifying it, that none of the columns $c_1, c_2, \ldots, c_n$ of $A$ is zero.

Prove that if $A$ is primitive, then $A^k$ is primitive for all $k \geqslant 1$.

Show that the spectral radius of a primitive matrix is strictly positive.

We define the matrix $W_n = (w_{i,j})$ in $\mathcal{M}_n(\mathbb{R})$ by $w_{i,j} = \begin{cases} 1 & \text{if } 1 \leqslant i < n \text{ and } j = i+1 \\ 1 & \text{if } i = n \text{ and } j \in \{1,2\} \\ 0 & \text{in all other cases} \end{cases}$
Specify the shortest circuit passing through index 1 in the matrix $W_n$.
Deduce that the positive matrix $W_n^{n^2-2n+1}$ is not strictly positive.

We define the matrix $W_n = (w_{i,j})$ in $\mathcal{M}_n(\mathbb{R})$ by $w_{i,j} = \begin{cases} 1 & \text{if } 1 \leqslant i < n \text{ and } j = i+1 \\ 1 & \text{if } i = n \text{ and } j \in \{1,2\} \\ 0 & \text{in all other cases} \end{cases}$
Show that for all $i, j$ in $\llbracket 1, n \rrbracket$, with $i \neq j$, there exists in $W_n$ at least one path with origin $i$, endpoint $j$, and length less than or equal to $n-1$.
You may treat successively the two cases $1 \notin \{i,j\}$ and $1 \in \{i,j\}$.
Deduce that the matrix $W_n^{n^2-2n+2}$ is strictly positive and conclude.

Throughout this subsection, $A$ is a given primitive matrix in $\mathcal{M}_n(\mathbb{R})$. We denote by $\ell \in \llbracket 1, n \rrbracket$ the smallest length of an elementary circuit of $A$.
By contradiction, we suppose $\ell = n$.
Show that then all circuits of $A$ have length a multiple of $n$. Deduce that the matrices $A^{kn+1}$ (with $k \in \mathbb{N}$) have zero diagonal and reach a contradiction.

Throughout this subsection, $A$ is a given primitive matrix in $\mathcal{M}_n(\mathbb{R})$. According to what precedes, there exists in $A$ an elementary circuit $\mathcal{C}$ of length $\ell \leqslant n-1$. To simplify the exposition, and because it does not affect the generality of the problem, we assume that it is the circuit $1 \rightarrow 2 \rightarrow \ldots \rightarrow \ell-1 \rightarrow \ell \rightarrow 1$ (the remaining $n-\ell$ indices $\ell+1, \ell+2, \ldots, n$ being thus located ``outside'' the circuit $\mathcal{C}$).
We will show that $A^{n+\ell(n-2)}$ is strictly positive. For this, we are given $i$ and $j$ in $\llbracket 1, n \rrbracket$. Everything comes down to establishing that there exists in $A$ a path with origin $i$, endpoint $j$ and length $n + \ell(n-2)$.
a) Show that in $A$, we can form a path with origin $i$, of length $n-\ell$, whose endpoint is in $\{1, 2, \ldots, \ell\}$ (we will denote by $k$ this endpoint). You may treat the case $1 \leqslant i \leqslant \ell$, then the case $\ell+1 \leqslant i \leqslant n$.
b) State the reason why the first $\ell$ diagonal coefficients of $A^\ell$ (and in particular the $k$-th) are strictly positive. Show then that there exists a path of length $n-1$ in $A^\ell$ (that is, a path of length $\ell(n-1)$ in $A$) with origin $k$ and endpoint $j$.
c) Finally deduce $A^{n+\ell(n-2)} > 0$, then $A^{n^2-2n+2} > 0$.

For any primitive matrix $A$ in $\mathcal{M}_n(\mathbb{R})$, the spectral radius $\rho(A)$ is a dominant eigenvalue of $A$ and the associated eigenspace is a line that possesses a strictly positive direction vector $x > 0$. We denote $r$ the spectral radius of $A$. We denote $x$ (respectively $y$) a strictly positive direction vector of the line $D = \operatorname{Ker}(A - rI_n)$ (respectively of the line $\Delta = \operatorname{Ker}(A^\top - rI_n)$). We denote $H = \operatorname{Im}(A - rI_n)$.
Show that $H$ is the hyperplane orthogonal to the line $\Delta$ (that is $H = \Delta^\perp$).

For any primitive matrix $A$ in $\mathcal{M}_n(\mathbb{R})$, the spectral radius $\rho(A)$ is a dominant eigenvalue of $A$ and the associated eigenspace is a line that possesses a strictly positive direction vector $x > 0$. We denote $r$ the spectral radius of $A$. We denote $x$ (respectively $y$) a strictly positive direction vector of the line $D = \operatorname{Ker}(A - rI_n)$ (respectively of the line $\Delta = \operatorname{Ker}(A^\top - rI_n)$). We denote $H = \operatorname{Im}(A - rI_n)$. If necessary by multiplying $y$ by an appropriate strictly positive coefficient, we assume $(y \mid x) = y^\top x = 1$. We denote $L = xy^\top$.
Prove that $L$ is the matrix, in the canonical basis, of the projection of $\mathbb{R}^n$ onto the line $D$, parallel to the hyperplane $H$.

For any primitive matrix $A$ in $\mathcal{M}_n(\mathbb{R})$, the spectral radius $\rho(A)$ is a dominant eigenvalue of $A$ and the associated eigenspace is a line that possesses a strictly positive direction vector $x > 0$. We denote $r$ the spectral radius of $A$. We denote $x$ (respectively $y$) a strictly positive direction vector of the line $D = \operatorname{Ker}(A - rI_n)$ (respectively of the line $\Delta = \operatorname{Ker}(A^\top - rI_n)$). We denote $H = \operatorname{Im}(A - rI_n)$. If necessary by multiplying $y$ by an appropriate strictly positive coefficient, we assume $(y \mid x) = y^\top x = 1$. We denote $L = xy^\top$.
Verify that $L$ has rank 1, that it is strictly positive, and that $L^\top y = y$.

For any primitive matrix $A$ in $\mathcal{M}_n(\mathbb{R})$, the spectral radius $\rho(A)$ is a dominant eigenvalue of $A$ and the associated eigenspace is a line that possesses a strictly positive direction vector $x > 0$. We denote $r$ the spectral radius of $A$. We denote $x$ (respectively $y$) a strictly positive direction vector of the line $D = \operatorname{Ker}(A - rI_n)$ (respectively of the line $\Delta = \operatorname{Ker}(A^\top - rI_n)$). We denote $H = \operatorname{Im}(A - rI_n)$. If necessary by multiplying $y$ by an appropriate strictly positive coefficient, we assume $(y \mid x) = y^\top x = 1$. We denote $L = xy^\top$.
Show that $AL = LA = rL$. Deduce: $\forall m \in \mathbb{N}^*, (A - rL)^m = A^m - r^m L$.

For any primitive matrix $A$ in $\mathcal{M}_n(\mathbb{R})$, we denote $r$ the spectral radius of $A$, $L = xy^\top$ where $x > 0$ is a direction vector of $\operatorname{Ker}(A - rI_n)$ and $y > 0$ is a direction vector of $\operatorname{Ker}(A^\top - rI_n)$ with $y^\top x = 1$. We set $B = A - rL$.
Let $\lambda$ be a nonzero eigenvalue of $B$ and let $z$ be an associated eigenvector.
Show that $Lz = 0$, then $Az = \lambda z$. Deduce $\rho(B) \leqslant r$.

For any primitive matrix $A$ in $\mathcal{M}_n(\mathbb{R})$, we denote $r$ the spectral radius of $A$, $L = xy^\top$ where $x > 0$ is a direction vector of $\operatorname{Ker}(A - rI_n)$ and $y > 0$ is a direction vector of $\operatorname{Ker}(A^\top - rI_n)$ with $y^\top x = 1$. We set $B = A - rL$.
Let $\lambda$ be a nonzero eigenvalue of $B$ and let $z$ be an associated eigenvector. By contradiction, we assume $\rho(B) = r$. We can therefore choose $\lambda$ such that $|\lambda| = r$. Show that then $\lambda = r$ then $Lz = z$ and reach a contradiction. Conclude.

For any primitive matrix $A$ in $\mathcal{M}_n(\mathbb{R})$, we denote $r$ the spectral radius of $A$, $L = xy^\top$ where $x > 0$ is a direction vector of $\operatorname{Ker}(A - rI_n)$ and $y > 0$ is a direction vector of $\operatorname{Ker}(A^\top - rI_n)$ with $y^\top x = 1$. We set $B = A - rL$, and we have shown $\rho(B) < r$ and $\forall m \in \mathbb{N}^*, (A - rL)^m = A^m - r^m L$.
Deduce from the above (and from subsection IV.A) that $\lim_{m \rightarrow +\infty} \left(\frac{1}{r}A\right)^m = L$.

For any primitive matrix $A$ in $\mathcal{M}_n(\mathbb{R})$, we denote $r$ the spectral radius of $A$. Let $\mu$ be the multiplicity of $r$ as an eigenvalue of $A$ and let $T = PAP^{-1}$ be a triangular reduction of $A$.
By examining the diagonal of $\left(\frac{1}{r}T\right)^m$ when $m \rightarrow +\infty$, show that $\mu = 1$.