Exercise 4 (Candidates who have followed the specialization course)
Two column matrices $\binom { x } { y }$ and $\binom { x ^ { \prime } } { y ^ { \prime } }$ with integer coefficients are said to be congruent modulo 5 if and only if $\left\{ \begin{array} { l } x \equiv x ^ { \prime } [ 5 ] \\ y \equiv y ^ { \prime } [ 5 ] \end{array} \right.$. Two square matrices of order $2 \left( \begin{array} { l l } a & c \\ b & d \end{array} \right)$ and $\left( \begin{array} { l l } a ^ { \prime } & c ^ { \prime } \\ b ^ { \prime } & d ^ { \prime } \end{array} \right)$ with integer coefficients are said to be congruent modulo 5 if and only if $\left\{ \begin{array} { l } a \equiv a ^ { \prime } [ 5 ] \\ b \equiv b ^ { \prime } [ 5 ] \\ c \equiv c ^ { \prime } [ 5 ] \\ d \equiv d ^ { \prime } [ 5 ] \end{array} \right.$.
Alice and Bob want to exchange messages using the procedure described below.

• They choose a square matrix M of order 2, with integer coefficients.
• Their initial message is written in capital letters without accents.
• Each letter of this message is replaced by a column matrix $\binom { x } { y }$ deduced from the table below: $x$ is the digit located at the top of the column and $y$ is the digit located to the left of the row; for example, the letter T in an initial message corresponds to the column matrix $\binom { 4 } { 3 }$.
• We calculate a new matrix $\binom { x ^ { \prime } } { y ^ { \prime } }$ by multiplying $\binom { x } { y }$ on the left by the matrix $M$:

$$\binom { x ^ { \prime } } { y ^ { \prime } } = \mathrm { M } \binom { x } { y } .$$

	0	1	2	3	4
0	A	B	C	D	E
1	F	G	H	I	J
2	K	L	M	N	O
3	P	Q	R	S	T
4	U	V	X	Y	Z

(A) Let $A$ and $B$ be $n \times n$ matrices with entries in $\mathbb{N}$. Show that if $B = A^{-1}$ then $A$ and $B$ are permutation matrices. (A permutation matrix is a matrix obtained by permuting the rows of the identity matrix.)
(B) Let $A$ be an $n \times n$ complex matrix that is not a scalar multiple of $I_n$. Show that $A$ is similar to a matrix $B$ such that $B_{1,1}$ (i.e. the top left entry of $B$) is 0.

What is the sum of all entries of the matrix representing the connection relationships between vertices of the following graph? [3 points]
(1) 6
(2) 8
(3) 10
(4) 12
(5) 14

A graph and the matrix representing the connection relationships between each vertex of the graph are as follows. What is the value of $a + b + c + d + e$?
A B C D E
$$\left( \begin{array} { l l l l l } 0 & 1 & 1 & 0 & a \\ 1 & 0 & 1 & b & 1 \\ 1 & 1 & c & 1 & 0 \\ 0 & d & 1 & 0 & 1 \\ e & 1 & 0 & 1 & 0 \end{array} \right)$$
(1) 1
(2) 2
(3) 3
(4) 4
(5) 5

In the following graph, how many zeros are there among the components of the matrix representing the connection relationships between vertices? [3 points]
(1) 9
(2) 11
(3) 13
(4) 15
(5) 17

Determine the matrices $M$ of $\mathcal { M } ( 2 , \mathbb { K } )$ that commute with $X _ { 0 }$. What are the matrices $M$ of $\mathcal { M } _ { 0 } ( 2 , \mathbb { K } )$ that commute with $X _ { 0 }$?
Recall that $X _ { 0 } = \left( \begin{array} { l l } 0 & 1 \\ 0 & 0 \end{array} \right)$, $H _ { 0 } = \left( \begin{array} { c c } 1 & 0 \\ 0 & - 1 \end{array} \right)$, $Y _ { 0 } = \left( \begin{array} { l l } 0 & 0 \\ 1 & 0 \end{array} \right)$, $J _ { 0 } = \left( \begin{array} { c c } 0 & 1 \\ - 1 & 0 \end{array} \right)$.

For all $n \in \mathbb{N}^*$, we define the matrix $H_n$ by: $$\forall (i,j) \in \llbracket 1; n \rrbracket^2, \quad (H_n)_{i,j} = \frac{1}{i+j-1}$$ We extend to $C^0([0;1], \mathbb{R})$ the inner product $\langle \cdot, \cdot \rangle$ by setting $$\forall f, g \in C^0([0;1], \mathbb{R}), \quad \langle f, g \rangle = \int_0^1 f(t) g(t) \, dt$$
Show that $H_n$ is the matrix of the inner product $\langle \cdot, \cdot \rangle$, restricted to $\mathbb{R}_{n-1}[X]$, in the canonical basis of $\mathbb{R}_{n-1}[X]$.

We set $\xi_i^j = \begin{cases}0 & \text{if } i = j \\ 1 & \text{otherwise}\end{cases}$ and $N_k = (m_{ij} + k\xi_i^j)$ with $k$ a strictly positive real number.
Express the matrix $N_k$ as a function of the matrices $M, J, I_n$ and the real $k$.

For $(a, b) \in \mathbb{C}^2$, we denote by $M(a, b)$ the square complex matrix $M(a, b) = \left( \begin{array}{cc} a & -b \\ \bar{b} & \bar{a} \end{array} \right) \in \mathcal{M}_2(\mathbb{C})$. A matrix of the form $M(a, b)$ will be called a quaternion. We will consider in particular the quaternions $e = I_2 = M(1, 0)$, $I = M(0, 1)$, $J = M(\mathrm{i}, 0)$, $K = M(0, -\mathrm{i})$ and we will denote by $\mathbb{H} = \{M(a, b) \mid (a, b) \in \mathbb{C}^2\}$ the subset of $\mathcal{M}_2(\mathbb{C})$ consisting of all quaternions. We equip the set $\mathcal{C} = \mathcal{M}_2(\mathbb{C})$ of complex matrices with two rows and two columns with addition $+$, multiplication $\times$ in the usual sense, and multiplication by a real number denoted $\cdot$. a) Give, without justification, a basis and the dimension of $\mathcal{C}$ over the field $\mathbb{R}$. b) Show that $\mathbb{H}$ is a real vector subspace of $\mathcal{C}$ and that $\{e, I, J, K\}$ is a basis for it over the field $\mathbb{R}$. c) Show that $\mathbb{H}$ is stable under multiplication.

Recall why $\mathcal{S}_{n}(\mathbb{R})$ is a real vector space and what is its dimension. Why is the map $s^{\downarrow}$ well-defined on $\mathcal{S}_{n}(\mathbb{R})$?

Prove that $\mathcal{Y}_n$ is a convex and compact subset of $\mathcal{M}_n(\mathbb{R})$.

Prove that $\mathcal{X}_2' = \mathcal{X}_2 \cap \mathrm{GL}_2(\mathbb{R})$ generates the vector space $\mathcal{M}_2$. For $n \geqslant 2$, does $\mathcal{X}_n'$ generate the vector space $\mathcal{M}_n(\mathbb{R})$?

Let $A$ be irreducible. Show that no row (and no column) of $A$ is identically zero.

We define the matrix $Z_n = (z_{i,j}) \in \mathcal{M}_n(\mathbb{R})$ by $z_{i,j} = \begin{cases} 1 & \text{if } 1 \leqslant i < n \text{ and } j = i+1 \\ 1 & \text{if } (i,j) \in \{(n-1,1),(n,2)\} \\ 0 & \text{in all other cases} \end{cases}$
Show that the matrix $Z_n$ is irreducible.

Give an example of a symmetric matrix $S$ in $\mathcal{S}_{2}(\mathbb{R})$ such that $\operatorname{sp}_{\mathbb{R}}(S) \subset [-1,1]$ and for which there does not exist a matrix $A \in \mathrm{O}_{2}(\mathbb{R})$ satisfying $A_{s} = S$.

Show that $\operatorname{Toep}_{n}(\mathbb{C})$ is a vector subspace of $\mathcal{M}_{n}(\mathbb{C})$. Give a basis for it and specify its dimension.

Let $A$ be a circulant matrix. Give a polynomial $P \in \mathbb{C}[X]$ such that $A = P(M_n)$.

Conversely, if $P \in \mathbb{C}[X]$, show, using a Euclidean division of $P$ by a suitably chosen polynomial, that $P(M_n)$ is a circulant matrix.

Show that the set of circulant matrices is a vector subspace of $\operatorname{Toep}_n(\mathbb{C})$, stable under multiplication and transposition.

Let $N = \left(\begin{array}{ccccc} 0 & 0 & \cdots & \cdots & 0 \\ 1 & 0 & & & \vdots \\ 0 & \ddots & \ddots & & \vdots \\ \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & \cdots & 0 & 1 & 0 \end{array}\right)$.
Show that the set of matrices that commute with $N$ is the set of lower triangular Toeplitz matrices.

What is the maximum cardinality of a set of nilpotent matrices, all of the same size $n$, such that there are no two similar matrices in this set?

Are the subsets $\mathrm{T}_{n}(\mathbb{K})$ and $\mathrm{T}_{n}^{+}(\mathbb{K})$ subalgebras of $\mathcal{M}_{n}(\mathbb{K})$?

Let $\Gamma(\mathbb{K})$ be the subset of $\mathcal{M}_{2}(\mathbb{K})$ consisting of matrices of the form $\left( \begin{array}{cc} a & -b \\ b & a \end{array} \right)$ where $(a, b) \in \mathbb{K}^{2}$.
Show that $\Gamma(\mathbb{K})$ is a subalgebra of $\mathcal{M}_{2}(\mathbb{K})$.

In this part, we assume $n \geqslant 2$. For all $(a_{0}, \ldots, a_{n-1}) \in \mathbb{R}^{n}$, we set $$J(a_{0}, \ldots, a_{n-1}) = \left( \begin{array}{cccc} a_{0} & a_{n-1} & \cdots & a_{1} \\ a_{1} & a_{0} & \cdots & a_{2} \\ \vdots & \vdots & & \vdots \\ a_{n-1} & a_{n-2} & \cdots & a_{0} \end{array} \right)$$ The coefficient with index $(i,j)$ of $J(a_{0}, \ldots, a_{n-1})$ is $a_{i-j}$ if $i \geqslant j$ and $a_{i-j+n}$ if $i < j$. Let $\mathcal{A}$ be the set of matrices of $\mathcal{M}_{n}(\mathbb{R})$ of the form $J(a_{0}, \ldots, a_{n-1})$ where $(a_{0}, \ldots, a_{n-1}) \in \mathbb{R}^{n}$. Let $J \in \mathcal{M}_{n}(\mathbb{R})$ be the matrix canonically associated with the endomorphism $\varphi \in \mathcal{L}(\mathbb{R}^{n})$ defined by $\varphi: e_{j} \mapsto e_{j+1}$ if $j \in \{1, \ldots, n-1\}$ and $\varphi(e_{n}) = e_{1}$, where $(e_{1}, \ldots, e_{n})$ is the canonical basis of $\mathbb{R}^{n}$.
What is the relationship between the matrix $J(a_{0}, \ldots, a_{n-1})$ and the $J^{k}$, where $0 \leqslant k \leqslant n-1$?

In this part, we assume $n \geqslant 2$. For all $(a_{0}, \ldots, a_{n-1}) \in \mathbb{R}^{n}$, we set $$J(a_{0}, \ldots, a_{n-1}) = \left( \begin{array}{cccc} a_{0} & a_{n-1} & \cdots & a_{1} \\ a_{1} & a_{0} & \cdots & a_{2} \\ \vdots & \vdots & & \vdots \\ a_{n-1} & a_{n-2} & \cdots & a_{0} \end{array} \right)$$ Let $\mathcal{A}$ be the set of matrices of $\mathcal{M}_{n}(\mathbb{R})$ of the form $J(a_{0}, \ldots, a_{n-1})$ where $(a_{0}, \ldots, a_{n-1}) \in \mathbb{R}^{n}$. Let $J \in \mathcal{M}_{n}(\mathbb{R})$ be the matrix canonically associated with the endomorphism $\varphi \in \mathcal{L}(\mathbb{R}^{n})$ defined by $\varphi: e_{j} \mapsto e_{j+1}$ if $j \in \{1, \ldots, n-1\}$ and $\varphi(e_{n}) = e_{1}$, where $(e_{1}, \ldots, e_{n})$ is the canonical basis of $\mathbb{R}^{n}$.
Show that $(I_{n}, J, J^{2}, \ldots, J^{n-1})$ is a basis of $\mathcal{A}$.