Encryption Method (Hill cipher)
The following table gives a correspondence between letters and numbers:
Encryption proceeds as follows:

1. We replace the letters with the values associated using the table above, and we place the pairs of numbers obtained in column matrices: $C _ { 1 } = \binom { 12 } { 0 }$, $C _ { 2 } = \binom { 19 } { 7 }$
2. We multiply the column matrices on the left by the matrix $A = \left( \begin{array} { l l } 9 & 4 \\ 7 & 3 \end{array} \right)$: $A C _ { 1 } = \binom { 108 } { 84 }$, $A C _ { 2 } = \binom { 199 } { 154 }$
3. We replace each coefficient of the column matrices obtained by its remainder in the Euclidean division by 26: $108 = 4 \times 26 + 4$, $84 = 3 \times 26 + 6$, we obtain $\binom { 4 } { 6 }$
4. We use the correspondence table between letters and numbers to obtain the encrypted word: EGRY

Question 1: By encrypting the word ``PION'' using this method, we obtain ``LZWH''. By detailing the steps for the letters ``ES'', encrypt the word ``ESPION''.
2. Decryption Method
Let $a, b, x, y, x^{\prime}$ and $y^{\prime}$ be relative integers. We know that if $x \equiv x^{\prime}$ modulo 26 and $y \equiv y^{\prime}$ modulo 26 then $ax + by \equiv ax^{\prime} + by^{\prime}$ modulo 26. This result allows us to write that, if $A$ is a $2 \times 2$ matrix, and $B$ and $C$ are two column matrices $2 \times 1$, then $B \equiv C$ modulo 26 implies $AB \equiv AC$ modulo 26.
a. Establish that the matrix $A = \left( \begin{array} { l l } 9 & 4 \\ 7 & 3 \end{array} \right)$ is invertible, and determine its inverse. b. Decrypt the word: XQGY.

Part A - Hill Cipher
Here are the different encryption steps for a word with an even number of letters:

Step 1	The word is divided into blocks of two consecutive letters, then for each block, each of the following steps is performed.
Step 2	To the two letters of the block are associated two integers $x_1$ and $x_2$ both between 0 and 25, which correspond to the two letters in the same order, in the following table: \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} A	B	C	D	E	F	G	H	I	J	K	L	M
0	1	2	3	4	5	6	7	8	9	10	11	12
N	O	P	Q	R	S	T	U	V	W	X	Y	Z
13	14	15	16	17	18	19	20	21	22	23	24	25

\hline Step 3 & The matrix $X = \binom{x_1}{x_2}$ is transformed into the matrix $Y = \binom{y_1}{y_2}$ satisfying $Y = AX$, where $A = \left(\begin{array}{ll} 5 & 2 \\ 7 & 7 \end{array}\right)$. \hline Step 4 & The matrix $Y = \binom{y_1}{y_2}$ is transformed into the matrix $R = \binom{r_1}{r_2}$, where $r_1$ is the remainder of the Euclidean division of $y_1$ by 26 and $r_2$ is the remainder of the Euclidean division of $y_2$ by 26. \hline Step 5 & To the integers $r_1$ and $r_2$ are associated the two corresponding letters from the table in step 2. The encrypted block is the block obtained by concatenating these two letters. \hline \end{tabular}
Use the encryption method presented to encrypt the word ``HILL''.
Part B - Some mathematical tools necessary for decryption

1. Let $a$ be an integer relatively prime to 26. Prove that there exists an integer $u$ such that $u \times a \equiv 1$ modulo 26.
   
2. Consider the following algorithm:
   

   VARIABLES : PROCESSING :	\begin{tabular}{l} $a, u$, and $r$ are numbers ($a$ is a natural number and relatively prime to 26)
   Read $a$
   $u$ takes the value 0, and $r$ takes the value 0
   While $r \neq 1$
   $u$ takes the value $u + 1$
   $r$ takes the value of the remainder of the Euclidean division of $u \times a$ by 26
   End While
   Display $u$

   \hline \end{tabular}
   The value $a = 21$ is entered into this algorithm. a. Reproduce on your paper and complete the following table, until the algorithm stops.
   

   $u$	0	1	2	$\ldots$
   $r$	0	21	$\ldots$	$\ldots$

   
   b. Deduce that $5 \times 21 \equiv 1$ modulo 26.
   
3. Recall that $A$ is the matrix $A = \left(\begin{array}{ll} 5 & 2 \\ 7 & 7 \end{array}\right)$ and denote by $I$ the matrix: $I = \left(\begin{array}{ll} 1 & 0 \\ 0 & 1 \end{array}\right)$. a. Calculate the matrix $12A - A^2$. b. Deduce the matrix $B$ such that $BA = 21I$. c. Prove that if $AX = Y$, then $21X = BY$.

Part C - Decryption
We want to decrypt the word VLUP. We denote by $X = \binom{x_1}{x_2}$ the matrix associated, according to the correspondence table, to a block of two letters before encryption, and $Y = \binom{y_1}{y_2}$ the matrix defined by the equality: $Y = AX = \left(\begin{array}{ll} 5 & 2 \\ 7 & 7 \end{array}\right) X$. If $r_1$ and $r_2$ are the respective remainders of $y_1$ and $y_2$ in the Euclidean division by 26, the block of two letters after encryption is associated with the matrix $R = \binom{r_1}{r_2}$.

1. Prove that: $\left\{ \begin{aligned} 21x_1 &= 7y_1 - 2y_2 \\ 21x_2 &= -7y_1 + 5y_2 \end{aligned} \right.$
   
2. Using question B.2., establish that: $\begin{cases} x_1 \equiv 9r_1 + 16r_2 & \text{modulo } 26 \\ x_2 \equiv 17r_1 + 25r_2 & \text{modulo } 26 \end{cases}$
   
3. Decrypt the word VLUP, associated with the matrices $\binom{21}{11}$ and $\binom{20}{15}$.

For this question write your answers as a series of four letters (Y for Yes and N for No) in order. Is it possible to find a $2 \times 2$ matrix $M$ for which the equation $M\vec{x} = \vec{p}$ has:
(a) no solutions for some but not all $\vec{p}$; exactly one solution for all other $\vec{p}$?
(b) exactly one solution for some but not all $\vec{p}$; more than one solution for all other $\vec{p}$?
(c) no solutions for some but not all $\vec{p}$; more than one solution for all other $\vec{p}$?
(d) no solutions for some $\vec{p}$, exactly one solution for some $\vec{p}$ and more than one solution for some $\vec{p}$?

For two matrices $A = \left( \begin{array} { l l } 1 & 2 \\ 2 & 5 \end{array} \right) , B = \left( \begin{array} { l l } 2 & - 3 \\ 1 & - 2 \end{array} \right)$, what is the sum of all components of matrix $X$ that satisfies $A X = B$? [2 points]
(1) $- 2$
(2) $- 1$
(3) 0
(4) 1
(5) 2

For two matrices $A = \left( \begin{array} { l l } 1 & 2 \\ 2 & 5 \end{array} \right) , B = \left( \begin{array} { l l } 2 & - 3 \\ 1 & - 2 \end{array} \right)$, what is the sum of all components of matrix $X$ that satisfies $A X = B$? [2 points]
(1) - 2
(2) - 1
(3) 0
(4) 1
(5) 2

For two matrices $A = \left( \begin{array} { r r } - 1 & 0 \\ 0 & 1 \end{array} \right) , B = \left( \begin{array} { l l } 2 & 1 \\ 3 & 3 \end{array} \right)$, what is the sum of all components of the matrix $( A + B ) ^ { - 1 }$? [2 points]
(1) 1
(2) 2
(3) 3
(4) 4
(5) 5

For a $2 \times 2$ square matrix $A$ satisfying $( A + E ) ^ { 2 } = A$ and a matrix $\binom { p } { q }$, $$\left( A + A ^ { - 1 } \right) \binom { p } { q } = \binom { 3 } { - 7 }$$ holds. Find the value of $p ^ { 2 } + q ^ { 2 }$. (Note: $E$ is the identity matrix.) [3 points]

For two matrices $A = \left( \begin{array} { r r } - 1 & 0 \\ 0 & 1 \end{array} \right) , B = \left( \begin{array} { l l } 2 & 1 \\ 3 & 3 \end{array} \right)$, what is the sum of all components of the matrix $( A + B ) ^ { - 1 }$? [2 points]
(1) 1
(2) 2
(3) 3
(4) 4
(5) 5

For the matrix $A = \left( \begin{array} { c c } 2 n & - 7 \\ - 1 & n \end{array} \right)$, what is the natural number $n$ such that all components of the inverse matrix $A ^ { - 1 }$ are natural numbers? [3 points]
(1) 1
(2) 2
(3) 3
(4) 4
(5) 5

A certain company converts the raw scores of applicants' reasoning ability test and spatial perception ability test for use. When the raw score of the reasoning ability test is $x$ and the raw score of the spatial perception ability test is $y$, the two converted scores $p$ and $q$ are as follows. $$\binom { p } { q } = \left( \begin{array} { l l } 3 & 2 \\ 2 & 3 \end{array} \right) \binom { x } { y }$$ When the converted scores of applicants A, B, and C are as shown in the table, let the raw scores of applicants A, B, and C on the reasoning ability test be $a , b , c$, respectively. Which of the following correctly represents the order of magnitude of $a , b , c$? [4 points]

Converted Score / Test Taker	A	B	C
$p$	45	50	45
$q$	40	50	50

(1) $a > b > c$
(2) $a > c > b$
(3) $b > a > c$
(4) $b > c > a$
(5) $c > b > a$

For the matrix $A = \left( \begin{array} { r r } 1 & - 2 \\ 0 & 1 \end{array} \right)$, what is the sum of all components of the inverse matrix $A ^ { - 1 }$? [2 points]
(1) 5
(2) 4
(3) 3
(4) 2
(5) 1

A $2 \times 2$ square matrix $A$ satisfies the following conditions. (where $E$ is the identity matrix and $O$ is the zero matrix)
(A) $A ^ { 2 } + 2 A - E = O$
(B) $A \binom { 1 } { - 1 } = \binom { 3 } { 4 }$ Find the value of $x + y$ for real numbers $x , y$ satisfying $( A + 2 E ) \binom { x } { y } = \binom { 3 } { - 3 }$. [4 points]

The sum of all components of the inverse matrix $A ^ { - 1 }$ of the matrix $A = \left( \begin{array} { r r } 1 & - 2 \\ 0 & 1 \end{array} \right)$ is? [2 points]
(1) 5
(2) 4
(3) 3
(4) 2
(5) 1

For the system of equations in $x, y$: $$\left( \begin{array} { c c } a + 1 & a \\ 1 & 1 \end{array} \right) \binom{x}{y} = \binom{-4}{1}$$ the solution satisfies the equation $x + 2y - 4a = 0$. What is the value of the constant $a$?
(1) 1
(2) 2
(3) 3
(4) 4
(5) 5

21. Elective 4-2: Matrices and Transformations
This problem mainly tests basic knowledge of matrices and inverse matrices, tests computational ability, and tests transformation and conversion ideas. Full marks: 7 points.
Solution: (1) Since $|A| = 2 \times 1 - (-1) \times 4 = 2$,
we have $A^{-1} = \begin{pmatrix} \frac{3}{2} & -\frac{1}{2} \\ -2 & 1 \end{pmatrix}$.
(2) From $AC = B$ we get $(A^{-1}A)C = A^{-1}B$,
thus $C = A^{-1}B = \begin{pmatrix} \frac{3}{2} & -\frac{1}{2} \\ -2 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 0 & -1 \end{pmatrix} = \begin{pmatrix} \frac{3}{2} & 2 \\ -2 & -3 \end{pmatrix}$.
Elective 4-4: Coordinate Systems and Parametric Equations
This problem mainly tests basic knowledge of conversion between polar and rectangular coordinates and parametric equations of circles, tests computational ability, and tests transformation and conversion ideas. Full marks: 7 points.
Solution: (1) Eliminating the parameter $t$, we obtain the ordinary equation of the circle: $(x-1)^2 + (y+2)^2 = 9$.
From $\sqrt{2}r\sin\left(q - \frac{p}{4}\right) = m$, we get $r\sin q - r\cos q - m = 0$,
so the rectangular coordinate equation of line $l$ is $x - y - m = 0$.
(2) According to the problem, the distance from center $C$ to line $l$ equals 2, i.e.,
$$\frac{|1 - (-2) - m|}{\sqrt{2}} = 2,$$
solving we get $m = -3 \pm 2\sqrt{2}$.
Elective 4-5: Inequalities
This problem mainly tests basic knowledge of absolute value inequalities and Cauchy inequality, tests reasoning and proof ability, and tests transformation and conversion ideas. Full marks: 7 points.
Solution: (1) Since $f(x) = |x+a| + |x+b| + c \geq |(

Prove that the real symmetric matrix $A$ is invertible. (One may consider the kernel of the map $x \mapsto A x$).

Prove that $\forall x , y \in \mathbb { R } ^ { n } , \left\langle A ^ { - 1 } x ; y \right\rangle = \left\langle x ; A ^ { - 1 } y \right\rangle$. Deduce that the matrix $A ^ { - 1 }$ is symmetric.

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$$ For each $n \in \mathbb{N}$, $\Pi_n$ denotes the unique polynomial in $\mathbb{R}_n[X]$ minimizing $\|Q - f\|$ over $\mathbb{R}_n[X]$.
Calculate the coefficients of $\Pi_n$ using the matrix $H_{n+1}^{-1}$ and the reals $\langle f, X^i \rangle$.

For $n \in \mathbb{N}^*$ and $(i,j) \in \llbracket 1, n \rrbracket^2$, we denote by $h_{i,j}^{(-1,n)}$ the coefficient at position $(i,j)$ of the matrix $H_n^{-1}$ and we denote by $s_n$ the sum of the coefficients of the matrix $H_n^{-1}$, that is: $$s_n = \sum_{1 \leqslant i,j \leqslant n} h_{i,j}^{(-1,n)}$$
Let $n \in \mathbb{N}^*$.
a) Show that there exists a unique $n$-tuple of real numbers $\left(a_p^{(n)}\right)_{0 \leqslant p \leqslant n-1}$ satisfying the following system of $n$ linear equations in $n$ unknowns: $$\left\{\begin{array}{ccccccc} a_0^{(n)} + & \frac{a_1^{(n)}}{2} + \cdots + \frac{a_{n-1}^{(n)}}{n} = & 1 \\ \frac{a_0^{(n)}}{2} + \frac{a_1^{(n)}}{3} + \cdots + \frac{a_{n-1}^{(n)}}{n+1} = & 1 \\ \vdots & \vdots & & \vdots \\ \frac{a_0^{(n)}}{n} + \frac{a_1^{(n)}}{n+1} + \cdots + \frac{a_{n-1}^{(n)}}{2n-1} = & 1 \end{array}\right.$$
b) Show that $s_n = \sum_{p=0}^{n-1} a_p^{(n)}$.

Show that if $S \in \mathcal{S}_n^{++}(\mathbb{R})$, then $S$ is invertible and $S^{-1} \in \mathcal{S}_n^{++}(\mathbb{R})$.

In this question, $f$ denotes the linear form defined by $\forall M \in \mathcal{M}_n(\mathbb{R}), f(M) = \sum_{j=1}^n \sum_{i=j}^n m_{i,j}$, and $A$ is the matrix such that $\forall M \in \mathcal{M}_n(\mathbb{R}), f(M) = \operatorname{Tr}(AM)$.
Show that $$A^{-1} = \left(\begin{array}{rrrrr} 1 & -1 & 0 & \cdots & 0 \\ 0 & 1 & -1 & \ddots & \vdots \\ \vdots & \ddots & 1 & \ddots & 0 \\ \vdots & & \ddots & \ddots & -1 \\ 0 & \cdots & \cdots & 0 & 1 \end{array}\right)$$

We assume that the conditions of question 12 are satisfied and that $\lambda(0) \neq 0$. Show that $H \in \mathrm{GL}(V)$.

We fix a matrix $A \in \mathcal{M}_d(\mathbb{R})$.
For $R$ large enough, show that, for every $\theta \in \mathbb{R}$, the matrix $(R\mathrm{e}^{\mathrm{i}\theta} I_d - A)$ is invertible in $\mathcal{M}_d(\mathbb{C})$, and that its inverse is the matrix $$\left(R\mathrm{e}^{\mathrm{i}\theta}\right)^{-1} \sum_{n=0}^{+\infty} \left(R\mathrm{e}^{\mathrm{i}\theta}\right)^{-n} A^n$$

Let $M = (x_1 | \cdots | x_n) \in \mathrm{GL}_n(\mathbb{R})$.
2a. Show that $M \in \mathrm{GL}_n(\mathbb{Z})$ if and only if $M(\mathbb{Z}^n) = \mathbb{Z}^n$.
2b. Show the equivalence of the following propositions:
i) $M \in \mathrm{GL}_n(\mathbb{Z})$.
ii) The integer points of the parallelepiped $\mathcal{P} = \left\{\sum_{i=1}^n t_i x_i \mid \forall i \in \{1,\ldots,n\}, t_i \in [0,1]\right\}$ are exactly the $2^n$ points $\sum_{i=1}^n \varepsilon_i x_i$, where $\varepsilon_i \in \{0,1\}$ for all $i \in \{1,\ldots,n\}$.

Let $M \in \mathscr{M}_{N,d}(\mathbb{R})$ defined by $M_{i,j} = g_{j}(i)$, $p \in \Sigma_{N}$, $m \in \mathbb{R}^{d}$, and $A \in \mathscr{M}_{d}(\mathbb{R})$ defined by $A_{lk} = \sum_{i=1}^{N} p_{i}(M_{il} - m_{l})(M_{ik} - m_{k})$. We denote by $\widetilde{M} = (M \mid \mathbf{1}) \in \mathscr{M}_{N,d+1}(\mathbb{R})$ the augmented matrix obtained by adding a column of 1s to the right of $M$.
Let $\theta \in \mathbb{R}^{d}$ such that $\theta^{T} A \theta = 0$. We assume that $p_{i} \neq 0$ for all $1 \leqslant i \leqslant N$.
(a) Show that there exists $c \in \mathbb{R}$, which you will specify, such that for all $i \in \{1, \ldots, N\}$, we have $\sum_{l=1}^{d} M_{il} \theta_{l} = c$.
(b) Show that if $\ker \widetilde{M} = \{0\}$ then $\theta = 0$.