Write in Python language a function \texttt{puiss2k} that takes as argument a square matrix $M$ and a natural integer $k$ and returns the matrix $M^{2^k}$ by performing $k$ matrix products. One may exploit the fact that $M^{2^{k+1}} = M^{2^k} M^{2^k}$.

Explain what the Python function \texttt{maxSp} defined by: \begin{verbatim} def maxSp(Q:np.ndarray, k:int, t:float) -> float: n = Q.shape[1] E = np.exp(t * np.array(range(n))) A = Q * E B = puiss2k(A, k) C = np.dot(A, B) return C.trace() / B.trace() \end{verbatim} does.

Let $$B = \frac{1}{4} \left(\begin{array}{cccc} 0 & -5 & 0 & -3 \\ 5 & 0 & 3 & 0 \\ 0 & -3 & 0 & -5 \\ 3 & 0 & 5 & 0 \end{array}\right).$$ Compute $B^{2} \left(\begin{array}{l} 1 \\ 1 \\ 1 \\ 1 \end{array}\right)$.

Show that, for every natural integer $k$, $P ^ { ( k + 1 ) } = P ^ { ( k ) } T$.

We consider the directed graph $G = ( S , A )$ where $$\left\{ \begin{array} { l } S = \{ 1,2,3,4 \} \\ A = \{ ( 1,2 ) , ( 2,1 ) , ( 1,3 ) , ( 3,1 ) , ( 1,4 ) , ( 4,1 ) , ( 2,3 ) , ( 3,2 ) , ( 2,4 ) , ( 4,2 ) , ( 3,4 ) , ( 4,3 ) \} \end{array} \right.$$ We assume that, when the point is on one of the vertices of the graph, it has the same probability of going to each of the three other vertices of the graph. Show that the sequence of matrices $\left( T ^ { k } \right) _ { k \in \mathbb { N } }$ converges and identify geometrically the endomorphism canonically associated with the limit matrix.

We consider the directed graph $G = ( S , A )$ where $$\left\{ \begin{array} { l } S = \{ 1,2,3,4 \} \\ A = \{ ( 1,2 ) , ( 2,1 ) , ( 1,3 ) , ( 3,1 ) , ( 1,4 ) , ( 4,1 ) , ( 2,3 ) , ( 3,2 ) , ( 2,4 ) , ( 4,2 ) , ( 3,4 ) , ( 4,3 ) \} \end{array} \right.$$ We assume that, when the point is on one of the vertices of the graph, it has the same probability of going to each of the three other vertices of the graph. Show that, for any row vector $P ^ { ( 0 ) } = \left( p _ { 1 } ^ { ( 0 ) } , p _ { 2 } ^ { ( 0 ) } , p _ { 3 } ^ { ( 0 ) } , p _ { 4 } ^ { ( 0 ) } \right)$, where for $1 \leqslant i \leqslant 4$, $p _ { i } ^ { ( 0 ) }$ is the probability that the point is initially on vertex $i$, the sequence $\left( P ^ { ( k ) } \right) _ { k \in \mathbb { N } }$ converges to the row vector $( 1 / 4,1 / 4,1 / 4,1 / 4 )$.

We now assume that all coefficients $m _ { i , j } ( 1 \leqslant i , j \leqslant n )$ of the stochastic matrix $M$ are strictly positive. We set $\varepsilon = \min _ { 1 \leqslant i , j \leqslant n } m _ { i , j }$. We are interested in the sequence $\left( M ^ { k } \right) _ { k \in \mathbb { N } }$ of powers of $M$. We denote by $m _ { i , j } ^ { ( k ) }$ the coefficient of the matrix $M ^ { k }$ located in row $i$ and column $j$.
For all $j \in \llbracket 1 , n \rrbracket$, we set $$\left\{ \begin{array} { l } \alpha _ { j } ^ { ( k ) } = \min _ { 1 \leqslant i \leqslant n } m _ { i , j } ^ { ( k ) } , \\ \beta _ { j } ^ { ( k ) } = \max _ { 1 \leqslant i \leqslant n } m _ { i , j } ^ { ( k ) } . \end{array} \right.$$
In the following four questions, $j$ is a fixed integer in $\llbracket 1 , n \rrbracket$ and $k$ is fixed in $\mathbb { N }$. Prove the inequalities $\alpha _ { j } ^ { ( k ) } \leqslant \alpha _ { j } ^ { ( k + 1 ) } \leqslant \beta _ { j } ^ { ( k + 1 ) } \leqslant \beta _ { j } ^ { ( k ) }$.

We now assume that all coefficients $m _ { i , j } ( 1 \leqslant i , j \leqslant n )$ of the stochastic matrix $M$ are strictly positive. We set $\varepsilon = \min _ { 1 \leqslant i , j \leqslant n } m _ { i , j }$.
Prove that the sequence $\left( M ^ { k } \right)$ converges to a stochastic matrix $B = \left( \begin{array} { l l l } b _ { 1 } & \cdots & b _ { n } \\ b _ { 1 } & \cdots & b _ { n } \\ b _ { 1 } & \cdots & b _ { n } \end{array} \right)$ all of whose rows are equal.

We model the web by a directed graph with $n$ vertices. The matrix $A$ is the stochastic matrix described in question 29. We define $$B = ( 1 - \alpha ) A + \frac { \alpha } { n } J _ { n }$$ where $J _ { n }$ is the matrix in $\mathcal { M } _ { n } ( \mathbb { R } )$ whose coefficients are all equal to $1$, $A$ is the stochastic matrix described in question 29 and $\alpha$ is a real number in $] 0,1 [$, called the damping factor.
Let $Q$ be a probability distribution. We define the sequence $\left( Q ^ { ( k ) } \right) _ { k \in \mathbb { N } }$ by $Q ^ { ( k ) } = Q B ^ { k }$ for every natural number $k$. Prove that the sequence $\left( Q ^ { ( k ) } \right) _ { k \in \mathbb { N } }$ converges and that its limit $Q ^ { \infty }$ satisfies conditions (i) and (ii) described in the introduction to this part. It thus provides relevance scores for the $n$ pages of the web. The relevance of each page $j$ will be expressed as a function of those of the pages pointing to it, distinguishing between pages that point to another page and the others.

For a triangular matrix $T = \left( \begin{array} { l l } \lambda & a \\ 0 & \mu \end{array} \right) \in \mathbf { M } _ { 2 } ( \mathbb { C } )$, explicitly compute the successive powers $T ^ { n }$ for $n$ a strictly positive integer.

For a triangular matrix $T = \left( \begin{array} { l l } \lambda & a \\ 0 & \mu \end{array} \right) \in \mathbf { M } _ { 2 } ( \mathbb { C } )$, explicitly compute the successive powers $T ^ { n }$ for $n$ a strictly positive integer.

Let $\mathscr{P}$ be the set of row vectors of size $d$ with non-negative coefficients whose coordinate sum equals 1: $$\mathscr{P} = \left\{ u \in \mathscr{M}_{1,d}\left(\mathbb{R}_{+}\right) : \sum_{j=1}^{d} u_j = 1 \right\}.$$ We consider a square matrix $P \in \mathscr{M}_d\left(\mathbb{R}_{+}\right)$ such that for all $i \in \{1,\ldots,d\}$, $$\sum_{j=1}^{d} P_{i,j} = 1$$ We further assume that there exist $\nu \in \mathscr{P}$ and $c > 0$ such that for all $i,j \in \{1,\ldots,d\}$, $$P_{i,j} \geqslant c\nu_j.$$ Let $\mu$ be the unique element of $\mathscr{P}$ such that $\mu P = \mu$.
Show that for all $n \in \mathbb{N}$ and all $x \in \mathscr{P}$, $$\left\| xP^n - \mu \right\|_1 \leqslant 2(1-c)^n.$$

Let $M \in \mathscr{M}_d\left(\mathbb{R}_{+}\right)$. We assume that the matrix $M$ has an eigenvalue $\lambda > 0$ and that there exists $h \in \mathscr{M}_{d,1}\left(\mathbb{R}_{+}^{*}\right)$ a column vector such that: $$Mh = \lambda h.$$ We also assume that there exist $\nu \in \mathscr{P}$ and $c > 0$ such that for all $i,j \in \{1,\ldots,d\}$, $$M_{i,j} \geqslant c\nu_j.$$ We introduce the matrix $P \in \mathscr{M}_d\left(\mathbb{R}_{+}\right)$ defined for $1 \leqslant i,j \leqslant d$ by $$P_{i,j} = \frac{M_{i,j} h_j}{\lambda h_i}.$$
Let $n \geqslant 1$. Give an expression for the coefficients of $P^n$ in terms of the coefficients of $M^n$, $h$ and $\lambda$.

In this part, we assume that $n \geqslant 4$. Let $u = (u_k)_{k \geqslant 0}$ be a sequence of $\mathbb{C}$ satisfying the condition $(C^\star)$: $R_u > 1$.
Let $F \in \mathscr{M}_n(\mathbb{C})$ be the matrix defined by $$[F]_{k,j} = \frac{1}{\sqrt{n}} \omega^{(k-1)(j-1)} \text{ for all } (k,j) \in \llbracket 1; n \rrbracket^2,$$ where $\omega = e^{-2\pi i/n}$ (here $i$ denotes the usual complex number satisfying $i^2 = -1$).
(a) Show that $F$ is invertible and that $F^{-1} = \bar{F}$.
(b) Show that $F^2 \in \mathscr{M}_n(\mathbb{R})$.
(c) Deduce that $F^4 = I_n$ and that $F \in \mathbb{M}_n(u)$.
(d) Deduce that $$\begin{aligned} u(F) = & \frac{1}{4}\left(U(1)(F + I_n) - U(-1)(F - I_n)\right)(F^2 + I_n) \\ & + \frac{i}{4}\left(U(i)(F + iI_n) - U(-i)(F - iI_n)\right)(F^2 - I_n) \end{aligned}$$

In this part, we assume that $n \geqslant 4$. Let $u = (u_k)_{k \geqslant 0}$ be a sequence of $\mathbb{C}$ satisfying the condition $(C^\star)$: $R_u > 1$.
Suppose that for all $k \in \mathbb{N}$, $u_k = \mathbb{P}(X = k)$ where $X$ is a random variable taking values in $\mathbb{N}$.
(a) Suppose that $X$ follows a binomial distribution with parameters $(N, p)$. Verify that $u$ satisfies condition $(C^\star)$ and find a simple expression for $u(A)$ for all $A \in \mathbb{M}_n(u)$.
(b) Suppose that $X$ follows a geometric distribution with parameter $p \in ]0,1[$. Verify that $u$ satisfies condition $(C^\star)$ and show that $$u(A) = p\left(I_n - (1-p)A\right)^{-1} A$$ for every diagonalizable matrix $A \in \mathbb{M}_n(u)$.

Problem 2, Part 2: Linear recurrence sequences with constant coefficients
We consider a sequence $\left( u _ { n } \right) _ { n \geqslant 0 }$ of complex numbers defined by the data of $u _ { 0 } , \ldots , u _ { d }$ and the linear recurrence relation $$u _ { n + d } = \sum _ { i = 0 } ^ { d - 1 } a _ { i } u _ { n + i } + b ,$$ where the $a _ { i }$ and $b$ are complex numbers. We define $P \in \mathbb { C } [ X ]$ by $P ( X ) = X ^ { d } - \sum _ { i = 0 } ^ { d - 1 } a _ { i } X ^ { i }$ and we assume that all complex roots of $P$ have modulus strictly less than 1.
For $n \geqslant 0$ we define the vector $U _ { n } \in \mathbb { C } ^ { d }$ by $U _ { n } = \left( u _ { n } , \ldots , u _ { n + d - 1 } \right)$ (recall that $U _ { n }$ is identified with a column vector). Show that the sequence $(U _ { n })$ satisfies a recurrence relation of the form $U _ { n + 1 } = A U _ { n } + B$, with $A \in \mathrm { M } _ { d } ( \mathbb { C } )$ and $B \in \mathbb { C } ^ { d }$ are elements that we shall specify.

For all $k \in \llbracket 1,n \rrbracket$, we denote by $C_{n,k}$ the matrix of $\mathcal{M}_n(\mathbb{R})$ defined by $$\forall (i,j) \in \llbracket 1,n \rrbracket^2, \quad C_{n,k}(i,j) = \begin{cases} 1 & \text{if } (i \in \llbracket 1,k \rrbracket \text{ and } j = i+n-k) \text{ or } (i \in \llbracket k+1,n \rrbracket \text{ and } j = i-k) \\ 0 & \text{otherwise} \end{cases}$$ We note that $C_{n,n} = I_n$. We set $J_n^{(1)} = C_{n,1} + C_{n,n-1}$.
Show that, for all $k \in \llbracket 1,n \rrbracket$, $C_{n,1}^k = C_{n,k}$.

In this subsection, we assume that $J_n = J_n^{(1)}$, the matrix introduced in subsection A-IV. We adopt the following convention: for all $x = (x_1, \ldots, x_n) \in \Lambda_n$, we denote $x_{n+1} = x_1$ and $x_0 = x_n$.
We set $A = \begin{pmatrix} \mathrm{e}^{\beta - h} & \mathrm{e}^{-\beta - h} \\ \mathrm{e}^{-\beta + h} & \mathrm{e}^{\beta + h} \end{pmatrix}$.
Show that $Z_n(h) = \operatorname{tr}(A^n)$, where $\operatorname{tr}$ denotes the trace of a square matrix.

Let $\theta = \frac{2\pi}{7}$ and consider the following matrix $$A = \left(\begin{array}{rr} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{array}\right)$$ If $A^n$ means $A \times \cdots \times A$ ($n$ times), then $A^{100}$ is
(A) $\left(\begin{array}{rr} \cos 2\theta & -\sin 2\theta \\ \sin 2\theta & \cos 2\theta \end{array}\right)$
(B) $\left(\begin{array}{rr} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{array}\right)$
(C) $\left(\begin{array}{ll} 1 & 0 \\ 0 & 1 \end{array}\right)$
(D) $\left(\begin{array}{rr} 0 & -1 \\ 1 & 0 \end{array}\right)$.

If $A = \left( \begin{array} { l l } 1 & 1 \\ 0 & i \end{array} \right)$ and $A ^ { 2018 } = \left( \begin{array} { l l } a & b \\ c & d \end{array} \right)$, then $a + d$ equals:
(A) $1 + i$
(B) 0
(C) 2
(D) 2018.

Let $\omega$ be a complex cube root of unity with $\omega \neq 1$ and $P = \left[ p _ { i j } \right]$ be a $n \times n$ matrix with $p _ { i j } = \omega ^ { i + j }$. Then $P ^ { 2 } \neq 0$, when $n =$
(A) 57
(B) 55
(C) 58
(D) 56

If $M = \left( \begin{array} { r r } \frac { 5 } { 2 } & \frac { 3 } { 2 } \\ - \frac { 3 } { 2 } & - \frac { 1 } { 2 } \end{array} \right)$, then which of the following matrices is equal to $M ^ { 2022 }$ ?
(A) $\quad \left( \begin{array} { r r } 3034 & 3033 \\ - 3033 & - 3032 \end{array} \right)$
(B) $\quad \left( \begin{array} { l l } 3034 & - 3033 \\ 3033 & - 3032 \end{array} \right)$
(C) $\quad \left( \begin{array} { r r } 3033 & 3032 \\ - 3032 & - 3031 \end{array} \right)$
(D) $\quad \left( \begin{array} { r r } 3032 & 3031 \\ - 3031 & - 3030 \end{array} \right)$

If $A = \left[ \begin{array} { c c } - 4 & - 1 \\ 3 & 1 \end{array} \right]$, then the determinant of the matrix $\left( A ^ { 2016 } - 2 A ^ { 2015 } - A ^ { 2014 } \right)$ is :
(1) $- 175$
(2) 2014
(3) 2016
(4) $- 25$

Let $\alpha$ be a root of the equation $x ^ { 2 } + x + 1 = 0$ and the matrix $A = \frac { 1 } { \sqrt { 3 } } \left[ \begin{array} { c c c } 1 & 1 & 1 \\ 1 & \alpha & \alpha ^ { 2 } \\ 1 & \alpha ^ { 2 } & \alpha ^ { 4 } \end{array} \right]$, then the matrix $A ^ { 31 }$ is equal to
(1) $A ^ { 3 }$
(2) $I _ { 3 }$
(3) $A ^ { 2 }$
(4) $A$

If $P = \left[ \begin{array} { c c } 1 & 0 \\ \frac { 1 } { 2 } & 1 \end{array} \right]$, then $P ^ { 50 }$ is:
(1) $\left[ \begin{array} { l l } 1 & 0 \\ 25 & 1 \end{array} \right]$
(2) $\left[ \begin{array} { l l } 1 & 50 \\ 0 & 1 \end{array} \right]$
(3) $\left[ \begin{array} { l l } 1 & 25 \\ 0 & 1 \end{array} \right]$
(4) $\left[ \begin{array} { l l } 1 & 0 \\ 50 & 1 \end{array} \right]$