Exercise 3 -- Candidates who have followed the specialization course

The manager of a website, composed of three web pages numbered 1 to 3 and linked together by hypertext links, wishes to predict the frequency of connection to each of his web pages.
Statistical studies have allowed him to notice that:

• If an internet user is on page no. 1, then he will go either to page no. 2 with probability $\frac{1}{4}$, or to page no. 3 with probability $\frac{3}{4}$.
• If an internet user is on page no. 2, then either he will go to page no. 1 with probability $\frac{1}{2}$ or he will stay on page no. 2 with probability $\frac{1}{4}$, or he will go to page no. 3 with probability $\frac{1}{4}$.
• If an internet user is on page no. 3, then either he will go to page no. 1 with probability $\frac{1}{2}$, or he will go to page no. 2 with probability $\frac{1}{4}$, or he will stay on page no. 3 with probability $\frac{1}{4}$.

For every natural number $n$, we define the following events and probabilities: $A_n$: ``After the $n$-th navigation, the internet user is on page no. 1'' and we denote $a_n = P(A_n)$. $B_n$: ``After the $n$-th navigation, the internet user is on page no. 2'' and we denote $b_n = P(B_n)$. $C_n$: ``After the $n$-th navigation, the internet user is on page no. 3'' and we denote $c_n = P(C_n)$.

1. Show that, for every natural number $n$, we have $a_{n+1} = \frac{1}{2}b_n + \frac{1}{2}c_n$.

We admit that, similarly, $b_{n+1} = \frac{1}{4}a_n + \frac{1}{4}b_n + \frac{1}{4}c_n$ and $c_{n+1} = \frac{3}{4}a_n + \frac{1}{4}b_n + \frac{1}{4}c_n$. Thus: $$\left\{\begin{aligned} a_{n+1} &= \frac{1}{2}b_n + \frac{1}{2}c_n \\ b_{n+1} &= \frac{1}{4}a_n + \frac{1}{4}b_n + \frac{1}{4}c_n \\ c_{n+1} &= \frac{3}{4}a_n + \frac{1}{4}b_n + \frac{1}{4}c_n \end{aligned}\right.$$

1. For every natural number $n$, we set $U_n = \begin{pmatrix}a_n\\b_n\\c_n\end{pmatrix}$. $U_0 = \begin{pmatrix}a_0\\b_0\\c_0\end{pmatrix}$ represents the initial situation, with $a_0 + b_0 + c_0 = 1$. Show that, for every natural number $n$, $U_{n+1} = MU_n$ where $M$ is a $3\times 3$ matrix that you will specify. Deduce that, for every natural number $n$, $U_n = M^n U_0$.
2. Show that there exists a unique column matrix $U = \begin{pmatrix}x\\y\\z\end{pmatrix}$ such that: $x + y + z = 1$ and $MU = U$.
3. A computer algebra system has made it possible to obtain the expression of $M^n$, $n$ being a non-zero natural number: $$M^n = \begin{pmatrix} \frac{1}{3} + \frac{\left(\frac{-1}{2}\right)^n \times 2}{3} & \frac{1}{3} + \frac{\left(\frac{-1}{2}\right)^n}{-3} & \frac{1}{3} + \frac{\left(\frac{-1}{2}\right)^n}{-3} \\ \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\ \frac{5}{12} + \frac{\left(-\left(\frac{-1}{2}\right)^n\right)\times 2}{3} & \frac{5}{12} + \frac{-\left(\frac{-1}{2}\right)^n}{-3} & \frac{5}{12} + \cdots \end{pmatrix}$$

3. For every natural integer $n$, we denote by $C _ { n }$ the column matrix $\binom { u _ { n + 1 } } { u _ { n } }$.
We denote by $A$ the square matrix of order 2 such that, for every natural integer $n$, $C _ { n + 1 } = A C _ { n }$. Determine $A$ and prove that, for every natural integer $n , C _ { n } = A ^ { n } C _ { 0 }$.
4. Let $P = \left( \begin{array} { l l } 2 & 3 \\ 1 & 1 \end{array} \right) , D = \left( \begin{array} { l l } 2 & 0 \\ 0 & 3 \end{array} \right)$ and $Q = \left( \begin{array} { c c } - 1 & 3 \\ 1 & - 2 \end{array} \right)$.
Calculate $Q P$. It is admitted that $A = P D Q$. Prove by induction that, for every non-zero natural integer $n , A ^ { n } = P D ^ { n } Q$.

A species of bird lives only on two islands A and B of an archipelago. At the beginning of 2013, 20 million birds of this species are present on island A and 10 million on island B.
Observations over several years have allowed ornithologists to estimate that, taking into account births, deaths, and migrations between the two islands, we find at the beginning of each year the following proportions:

• on island A: $80\%$ of the number of birds present on island A at the beginning of the previous year and $30\%$ of the number of birds present on island B at the beginning of the previous year;
• on island B: $20\%$ of the number of birds present on island A at the beginning of the previous year and $70\%$ of the number of birds present on island B at the beginning of the previous year.

Exercise 4 — Candidates who have followed the specialization course
In an imaginary isolated village, a new contagious but non-fatal disease has appeared. Scientists discovered that an individual could be in one of three following states:

• $S$: ``the individual is healthy, that is, not sick and not infected'',
• $I$: ``the individual is a healthy carrier, that is, not sick but infected'',
• $M$: ``the individual is sick and infected''.

Part A
Scientists estimate that a single individual is at the origin of the disease among the 100 people in the population and that, from one week to the next, an individual changes state according to the following process:

• among healthy individuals, the proportion of those who become healthy carriers is equal to $\dfrac{1}{3}$ and the proportion of those who become sick is equal to $\dfrac{1}{3}$,
• among healthy carriers, the proportion of those who become sick is equal to $\dfrac{1}{2}$.

We denote by $P_n = \begin{pmatrix} s_n & i_n & m_n \end{pmatrix}$ the row matrix giving the probabilistic state after $n$ weeks where $s_n, i_n$ and $m_n$ denote respectively the probability that the individual is healthy, a healthy carrier, or sick in the $n$-th week.
We have $P_0 = (0.99 \quad 0 \quad 0.01)$ and for all natural integer $n$, $$\left\{\begin{aligned} s_{n+1} &= \frac{1}{3}s_n \\ i_{n+1} &= \frac{1}{3}s_n + \frac{1}{2}i_n \\ m_{n+1} &= \frac{1}{3}s_n + \frac{1}{2}i_n + m_n \end{aligned}\right.$$

1. Write the matrix $A$ called the transition matrix, such that for all natural integer $n$, $P_{n+1} = P_n \cdot A$.

(For candidates who have followed the specialization course)
As part of a study on social interactions between mice, researchers place laboratory mice in a cage with two compartments A and B. The door between these compartments is opened for ten minutes every day at noon. We study the distribution of mice in the two compartments. It is estimated that each day:

• $20\%$ of the mice present in compartment A before the door opens are found in compartment B after the door closes,
• $10\%$ of the mice that were in compartment B before the door opens are found in compartment A after the door closes.

We assume that initially, the two compartments A and B contain the same number of mice. We set $a_{0} = 0.5$ and $b_{0} = 0.5$. For all natural integer $n$ greater than or equal to 1, we denote by $a_{n}$ and $b_{n}$ the proportions of mice present respectively in compartments A and B after $n$ days, after the door closes. We denote by $U_{n}$ the matrix $\binom{a_{n}}{b_{n}}$.

1. Let $n$ be a natural integer. a. Justify that $U_{1} = \binom{0.45}{0.55}$. b. Express $a_{n+1}$ and $b_{n+1}$ as functions of $a_{n}$ and $b_{n}$. c. Deduce that $U_{n+1} = MU_{n}$ where $M$ is a matrix that we will specify. We admit without proof that $U_{n} = M^{n}U_{0}$. d. Determine the distribution of mice in compartments A and B after 3 days.
2. Let the matrix $P = \left(\begin{array}{cc} 1 & 1 \\ 2 & -1 \end{array}\right)$. a. Calculate $P^{2}$. Deduce that $P$ is invertible and $P^{-1} = \frac{1}{3}P$. b. Verify that $P^{-1}MP$ is a diagonal matrix $D$ that we will specify. c. Prove that for any natural integer $n$ greater than or equal to 1, $M^{n} = PD^{n}P^{-1}$. Using computer algebra software, we obtain $$M^{n} = \left(\begin{array}{cc} \frac{1 + 2 \times 0.7^{n}}{3} & \frac{1 - 0.7^{n}}{3} \\ \frac{2 - 2 \times 0.7^{n}}{3} & \frac{2 + 0.7^{n}}{3} \end{array}\right).$$
3. Using the help of the previous questions, what can we say about the long-term distribution of mice in compartments A and B of the cage?

Exercise 2 — Candidates who have not followed the specialization course
We place ourselves in an orthonormal frame and, for every natural integer $n$, we define the points $\left( A _ { n } \right)$ by their coordinates $\left( x _ { n } ; y _ { n } \right)$ in the following way:
$$\left\{ \begin{array} { l } x _ { 0 } = - 3 \\ y _ { 0 } = 4 \end{array} \text { and for every natural integer } n : \left\{ \begin{array} { l } x _ { n + 1 } = 0,8 x _ { n } - 0,6 y _ { n } \\ y _ { n + 1 } = 0,6 x _ { n } + 0,8 y _ { n } \end{array} \right. \right.$$

1. a. Determine the coordinates of the points $A _ { 0 } , A _ { 1 }$ and $A _ { 2 }$. b. Copy and complete the following algorithm so that it constructs the points $A _ { 0 }$ to $A _ { 20 }$: \begin{verbatim} Variables : i,x,y,t: real numbers Initialization : x takes the value -3 y takes the value 4 Processing : For i ranging from 0 to 20 Construct the point with coordinates (x;y) t takes the value x x takes the value .... y takes the value .... End For \end{verbatim} c. Identify the points $A _ { 0 } , A _ { 1 }$ and $A _ { 2 }$ on the point cloud figure. What appears to be the set to which the points $A _ { n }$ belong for every natural integer $n$?
2. The purpose of this question is to construct geometrically the points $A _ { n }$ for every natural integer $n$. In the complex plane, we denote, for every natural integer $n$, $z _ { n } = x _ { n } + \mathrm { i } y _ { n }$ the affix of the point $A _ { n }$. a. Let $u _ { n } = \left| z _ { n } \right|$. Show that, for every natural integer $n , u _ { n } = 5$. What geometric interpretation can be made of this result? b. We admit that there exists a real number $\theta$ such that $\cos ( \theta ) = 0,8$ and $\sin ( \theta ) = 0,6$. Show that, for every natural integer $n , \mathrm { e } ^ { \mathrm { i } \theta } z _ { n } = z _ { n + 1 }$. c. Prove that, for every natural integer $n , z _ { n } = \mathrm { e } ^ { \mathrm { i } n \theta } z _ { 0 }$. d. Show that $\theta + \frac { \pi } { 2 }$ is an argument of the complex number $z _ { 0 }$. e. For every natural integer $n$, determine, as a function of $n$ and $\theta$, an argument of the complex number $z _ { n }$. Explain, for every natural integer $n$, how to construct the point $A _ { n + 1 }$ from the point $A _ { n }$.

Exercise 2 — Candidates who have followed the specialization course
We are given the matrices $M = \left( \begin{array} { c c c } 1 & 1 & 1 \\ 1 & - 1 & 1 \\ 4 & 2 & 1 \end{array} \right)$ and $I = \left( \begin{array} { l l l } 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right)$.

Part A

1. Determine the matrix $M ^ { 2 }$. We are given $M ^ { 3 } = \left( \begin{array} { c c c } 20 & 10 & 11 \\ 12 & 2 & 9 \\ 42 & 20 & 21 \end{array} \right)$.
2. Verify that $M ^ { 3 } = M ^ { 2 } + 8 M + 6 I$.
3. Deduce that $M$ is invertible and that $M ^ { - 1 } = \frac { 1 } { 6 } \left( M ^ { 2 } - M - 8 I \right)$.

Part B Study of a particular case

We seek to determine three integers $a , b$ and $c$ such that the parabola with equation $y = a x ^ { 2 } + b x + c$ passes through the points $\mathrm { A } ( 1 ; 1 ) , \mathrm { B } ( - 1 ; - 1 )$ and $\mathrm { C } ( 2 ; 5 )$.

1. Prove that the problem amounts to finding three integers $a , b$ and $c$ such that $$M \left( \begin{array} { l } a \\ b \\ c \end{array} \right) = \left( \begin{array} { c } 1 \\ - 1 \\ 5 \end{array} \right)$$
2. Calculate the numbers $a$, $b$ and $c$ and verify that these numbers are integers.

Part C Return to the general case

The numbers $a , b , c , p , q , r$ are integers. In a frame ( $\mathrm { O } , \vec { \imath } , \vec { \jmath }$ ), we consider the points $\mathrm { A } ( 1 ; p ) , \mathrm { B } ( - 1 ; q )$ and $\mathrm { C } ( 2 ; r )$. We seek values of $p , q$ and $r$ for which there exists a parabola with equation $y = a x ^ { 2 } + b x + c$ passing through A, B and C.

1. Prove that if $\left( \begin{array} { l } a \\ b \\ c \end{array} \right) = M ^ { - 1 } \left( \begin{array} { c } p \\ q \\ r \end{array} \right)$ with $a , b$ and $c$ integers, then $$\begin{cases} - 3 p + q + 2 r & \equiv 0 [ 6 ] \\ 3 p - 3 q & \equiv 0 [ 6 ] \\ 6 p + 2 q - 2 r & \equiv 0 [ 6 ] \end{cases}$$
2. Deduce that $\left\{ \begin{array} { l l l } q - r & \equiv & 0 [ 3 ] \\ p - q & \equiv & 0 [ 2 ] \end{array} \right.$.
3. Conversely, we admit that if $\left\{ \begin{array} { l } q - r \equiv 0 [ 3 ] \\ p - q \equiv 0 [ 2 ] \\ \mathrm { A } , \mathrm { B } , \mathrm { C } \text{ are not collinear} \end{array} \right.$ then there exist three integers $a , b$ and $c$ such that the parabola with equation $y = a x ^ { 2 } + b x + c$ passes through the points $\mathrm { A } , \mathrm { B }$ and C. a. Show that the points $\mathrm { A } , \mathrm { B }$ and C are collinear if and only if $2 r + q - 3 p = 0$. b. We choose $p = 7$. Determine integers $q , r , a , b$ and $c$ such that the parabola with equation $y = a x ^ { 2 } + b x + c$ passes through the points $\mathrm { A } , \mathrm { B }$ and C.

Exercise 5 — Candidates who have chosen the specialisation option
Consider the matrix $A = \left( \begin{array} { l l } - 4 & 6 \\ - 3 & 5 \end{array} \right)$.

1. We call $I$ the identity matrix of order 2.
   Verify that $A ^ { 2 } = A + 2 I$.
2. Deduce an expression for $A ^ { 3 }$ and an expression for $A ^ { 4 }$ in the form $\alpha A + \beta I$ where $\alpha$ and $\beta$ are real numbers.
3. Consider the sequences $\left( r _ { n } \right)$ and $\left( s _ { n } \right)$ defined by $r _ { 0 } = 0$ and $s _ { 0 } = 1$ and, for all natural integer $n$,
   $$\left\{ \begin{array} { l } r _ { n + 1 } = r _ { n } + s _ { n } \\ s _ { n + 1 } = 2 r _ { n } \end{array} \right.$$
   Prove that, for all natural integer $n , A ^ { n } = r _ { n } A + s _ { n } I$.
4. Prove that the sequence ( $k _ { n }$ ) defined for all natural integer $n$ by $k _ { n } = r _ { n } - s _ { n }$ is geometric with common ratio $- 1$. Deduce, for all natural integer $n$, an explicit expression for $k _ { n }$ as a function of $n$.
5. We admit that the sequence ( $t _ { n }$ ) defined for all natural integer $n$ by $t _ { n } = r _ { n } + \frac { ( - 1 ) ^ { n } } { 3 }$ is geometric with common ratio 2. Deduce, for all natural integer $n$, an explicit expression for $t _ { n }$ as a function of $n$.
6. From the previous questions, deduce, for all natural integer $n$, an explicit expression for $r _ { n }$ and $s _ { n }$ as a function of $n$.
7. Deduce then, for all natural integer $n$, an expression for $A ^ { n }$.

Part A

We consider matrices $M$ of the form $M = \left( \begin{array} { l l } a & b \\ 5 & 3 \end{array} \right)$ where $a$ and $b$ are integers. The number $3 a - 5 b$ is called the determinant of $M$. We denote it $\operatorname { det } ( M )$. Thus $\operatorname { det } ( M ) = 3 a - 5 b$.

1. In this question we assume that $\operatorname { det } ( M ) \neq 0$ and we set $N = \frac { 1 } { \operatorname { det } ( M ) } \left( \begin{array} { c c } 3 & - b \\ - 5 & a \end{array} \right)$. Justify that $N$ is the inverse of $M$.
2. We consider the equation $( E ) : \quad \operatorname { det } ( M ) = 3$.
   We wish to determine all pairs of integers ( $a ; b$ ) that are solutions of equation ( $E$ ). a. Verify that the pair (6; 3) is a solution of $( E )$. b. Show that the pair of integers ( $a$; $b$ ) is a solution of ( $E$ ) if and only if $3 ( a - 6 ) = 5 ( b - 3 )$. Deduce the set of solutions of equation ( $E$ ).

Part B

1. We set $Q = \left( \begin{array} { l l } 6 & 3 \\ 5 & 3 \end{array} \right)$.
   Using Part A, determine the inverse matrix of $Q$.
2. Encoding with matrix $Q$
   To encode a two-letter word using the matrix $Q = \left( \begin{array} { l l } 6 & 3 \\ 5 & 3 \end{array} \right)$ we use the following procedure: Step 1: We associate with the word the matrix $X = \binom { x _ { 1 } } { x _ { 2 } }$ where $x _ { 1 }$ is the integer corresponding to the first letter of the word and $x _ { 2 }$ the integer corresponding to the second letter of the word according to the correspondence table below:
   

   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

   
   Step 2: The matrix $X$ is transformed into the matrix $Y = \binom { y _ { 1 } } { y _ { 2 } }$ such that $Y = Q X$. Step 3: The matrix $Y$ is transformed into the matrix $R = \binom { r _ { 1 } } { r _ { 2 } }$ such that $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.

The complex plane is equipped with an orthonormal coordinate system ($\mathrm{O}; \vec{u}, \vec{v}$). We consider the line $\mathscr{D}$ with equation $$7x - 3y - 1 = 0$$ We define the sequence $(A_{n})$ of points in the plane with coordinates $(x_{n}; y_{n})$ satisfying for all natural integer $n$: $$\left\{ \begin{array}{l} x_{0} = 1 \\ y_{0} = 2 \end{array} \quad \text{and} \quad \left\{ \begin{array}{l} x_{n+1} = -\frac{13}{2} x_{n} + 3 y_{n} \\ y_{n+1} = -\frac{35}{2} x_{n} + 8 y_{n} \end{array} \right. \right.$$
We denote by $M$ the matrix $\left( \begin{array}{cc} \frac{-13}{2} & 3 \\ \frac{-35}{2} & 8 \end{array} \right)$.

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.

Exercise 4 — For candidates who have followed the speciality course Part A We consider the sequence $(u_{n})$ defined by: $u_{0} = 1,\ u_{1} = 6$ and, for every natural number $n$: $$u_{n+2} = 6u_{n+1} - 8u_{n}$$

1. Calculate $u_{2}$ and $u_{3}$.
2. We consider the matrix $A = \left(\begin{array}{cc} 0 & 1 \\ -8 & 6 \end{array}\right)$ and the column matrix $U_{n} = \binom{u_{n}}{u_{n+1}}$. Show that, for every natural number $n$, we have: $U_{n+1} = A U_{n}$.
3. We also consider the matrices $B = \left(\begin{array}{cc} 2 & -0.5 \\ 4 & -1 \end{array}\right)$ and $C = \left(\begin{array}{cc} -1 & 0.5 \\ -4 & 2 \end{array}\right)$. a. Show by induction that, for every natural number $n$, we have: $A^{n} = 2^{n}B + 4^{n}C$. b. We admit that, for every natural number $n$, we have: $U_{n} = A^{n}U_{0}$. Show that, for every natural number $n$, we have: $u_{n} = 2 \times 4^{n} - 2^{n}$.

Part B We say that a natural number $N$ is perfect when the sum of its (positive) divisors equals $2N$. For example, 6 is a perfect number because its divisors are $1, 2, 3$ and 6 and we have: $1 + 2 + 3 + 6 = 12 = 2 \times 6$. In this part, we seek perfect numbers among the terms of the sequence $(u_{n})$ studied in Part A.

1. Verify that, for every natural number $n$, we have: $u_{n} = 2^{n}p_{n}$ with $p_{n} = 2^{n+1} - 1$.
2. We consider the following algorithm where $N, S, U, P$ and $K$ are natural numbers.

Exercise 4 (For candidates who have followed the specialty course)

We denote $\mathbb{Z}$ the set of integers. In this exercise, we study the set $S$ of matrices that can be written in the form $A = \left(\begin{array}{cc} a & b \\ c & d \end{array}\right)$, where $a, b, c$ and $d$ belong to the set $\mathbb{Z}$ and satisfy: $ad - bc = 1$. We denote $I$ the identity matrix $I = \left(\begin{array}{ll} 1 & 0 \\ 0 & 1 \end{array}\right)$.

Part A

1. Verify that the matrix $A = \left(\begin{array}{rr} 6 & 5 \\ -5 & -4 \end{array}\right)$ belongs to the set $S$.
2. Show that there exist exactly four matrices of the form $A = \left(\begin{array}{ll} a & 2 \\ 3 & d \end{array}\right)$ belonging to the set $S$; state them explicitly.
3. a. Solve in $\mathbb{Z}$ the equation $(E): 5x - 2y = 1$. We may note that the pair $(1; 2)$ is a particular solution of this equation. b. Deduce that there exist infinitely many matrices of the form $A = \left(\begin{array}{cc} a & b \\ 2 & 5 \end{array}\right)$ that belong to the set $S$. Describe these matrices.

Part B

In this part, we denote $A = \left(\begin{array}{ll} a & b \\ c & d \end{array}\right)$ a matrix belonging to the set $S$. We recall that $a$, $b$, $c$ and $d$ are integers such that $ad - bc = 1$.

1. Show that the integers $a$ and $b$ are coprime.
2. Let $B$ be the matrix: $B = \left(\begin{array}{rr} d & -b \\ -c & a \end{array}\right)$ a. Calculate the product $AB$. It is admitted that $AB = BA$. b. Deduce that the matrix $A$ is invertible and give its inverse matrix $A^{-1}$. c. Show that $A^{-1}$ belongs to the set $S$.
3. Let $x$ and $y$ be two integers. We denote $x'$ and $y'$ the integers such that $\binom{x'}{y'} = A\binom{x}{y}$. a. Show that $x = dx' - by'$. It is admitted that likewise $y = ay' - cx'$. b. We denote $D$ the GCD of $x$ and $y$ and we denote $D'$ the GCD of $x'$ and $y'$. Show that $D = D'$.
4. We consider the sequences of natural numbers $(x_n)$ and $(y_n)$ defined by: $x_0 = 2019$, $y_0 = 673$ and for any natural number $n$: $$\left\{\begin{array}{l} x_{n+1} = 2x_n + 3y_n \\ y_{n+1} = x_n + 2y_n \end{array}\right.$$ Using the previous question, determine, for any natural number $n$, the GCD of the integers $x_n$ and $y_n$.

Exercise 4 — For candidates who have followed the speciality course
We consider the matrix $M = \left( \begin{array} { l l } 2 & 3 \\ 1 & 2 \end{array} \right)$ and the sequences of natural numbers $\left( u _ { n } \right)$ and $\left( v _ { n } \right)$ defined by: $u _ { 0 } = 1 , v _ { 0 } = 0$, and for every natural number $n , \binom { u _ { n + 1 } } { v _ { n + 1 } } = M \binom { u _ { n } } { v _ { n } }$. The two parts can be treated independently.

Part A

The first terms of the sequence $\left( v _ { n } \right)$ have been calculated:

$n$	0	1	2	3	4	5	6	7	8	9	10	11	12
$v _ { n }$	0	1	4	15	56	209	780	2911	10864	40545	151316	564719	2107560

1. Conjecture the possible values of the units digit of the terms of the sequence $\left( v _ { n } \right)$.
2. It is admitted that for every natural number $n , \binom { u _ { n + 3 } } { v _ { n + 3 } } = M ^ { 3 } \binom { u _ { n } } { v _ { n } }$. a. Justify that for every natural number $n , \left\{ \begin{array} { l } u _ { n + 3 } = 26 u _ { n } + 45 v _ { n } \\ v _ { n + 3 } = 15 u _ { n } + 26 v _ { n } \end{array} \right.$. b. Deduce that for every natural number $n : v _ { n + 3 } \equiv v _ { n } [ 5 ]$.
3. Let $r$ be a fixed natural number. Prove, using a proof by induction, that, for every natural number $q , v _ { 3 q + r } \equiv v _ { r }$ [5].
4. Deduce that for every natural number $n$ the term $v _ { n }$ is congruent to 0, to 1 or to 4 modulo 5.
5. Conclude regarding the set of values taken by the units digit of the terms of the sequence $\left( v _ { n } \right)$.

Part B

The objective of this part is to prove that $\sqrt { 3 }$ is not a rational number using the matrix $M$.
To do this, we perform a proof by contradiction and assume that $\sqrt { 3 }$ is a rational number. In this case, $\sqrt { 3 }$ can be written in the form of an irreducible fraction $\frac { p } { q }$ where $p$ and $q$ are non-zero natural numbers, with $q$ the smallest possible natural number.

1. Show that $q < p < 2 q$.
2. It is admitted that the matrix $M$ is invertible. Give its inverse $M ^ { - 1 }$ (no justification is expected). Let the pair $\left( p ^ { \prime } ; q ^ { \prime } \right)$ be defined by $\binom { p ^ { \prime } } { q ^ { \prime } } = M ^ { - 1 } \binom { p } { q }$.
3. a. Verify that $p ^ { \prime } = 2 p - 3 q$ and that $q ^ { \prime } = - p + 2 q$. b. Justify that ( $p ^ { \prime } ; q ^ { \prime }$ ) is a pair of relative integers. c. Recall that $p = q \sqrt { 3 }$. Show that $p ^ { \prime } = q ^ { \prime } \sqrt { 3 }$. d. Show that $0 < q ^ { \prime } < q$. e. Deduce that $\sqrt { 3 }$ is not a rational number.

A matriz $A = \begin{pmatrix} 2 & 1 \\ 3 & 4 \end{pmatrix}$ tem determinante igual a
(A) 2 (B) 3 (C) 5 (D) 8 (E) 11

A student recorded the bimonthly grades of some of his subjects in a table. He observed that the numerical entries in the table formed a $4 \times 4$ matrix, and that he could calculate the annual averages of these subjects using matrix multiplication. All tests had the same weight, and the table he obtained is shown below.

	$1^{st}$ bimonth	$2^{nd}$ bimonth	$3^{rd}$ bimonth	$4^{th}$ bimonth
Mathematics	5.9	6.2	4.5	5.5
Portuguese	6.6	7.1	6.5	8.4
Geography	8.6	6.8	7.8	9.0
History	6.2	5.6	5.9	7.7

To obtain these averages, he multiplied the matrix obtained from the table by
(A) $\left[\frac{1}{2}\quad\frac{1}{2}\quad\frac{1}{2}\quad\frac{1}{2}\right]$

QUESTION 156
The matrix $A = \begin{pmatrix} 2 & 1 \\ 3 & 4 \end{pmatrix}$ has determinant
(A) 2
(B) 3
(C) 4
(D) 5
(E) 6

The matrix $A = \begin{pmatrix} 2 & 1 \\ 3 & 4 \end{pmatrix}$ has determinant:
(A) 2
(B) 3
(C) 4
(D) 5
(E) 6

There exists a real $3 \times 3$ orthogonal matrix with only non-zero entries.

(a) Show that there exists a $3 \times 3$ invertible matrix $M \neq I _ { 3 }$ with entries in the field $\mathbb { F } _ { 2 }$ such that $M ^ { 7 } = I _ { 3 }$.
(b) Let $A$ be an $m \times n$ matrix, and $\mathbf { b }$ an $m \times 1$ vector, both with integer entries.

1. Suppose that there exists a prime number $p$ such that the equation $A \mathbf { x } = \mathbf { b }$ seen as an equation over the finite field $\mathbb { F } _ { p }$ has a solution. Then does there exist a solution to $A \mathbf { x } = \mathbf { b }$ over the real numbers?
2. If $A \mathbf { x } = \mathbf { b }$ has a solution over $\mathbb { F } _ { p }$ for every prime $p$, is a real solution guaranteed?

(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.

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}$?

$M$ is a $3 \times 3$ matrix with integer entries. For $M$ we have (Sum of column 2) $= 4 \times$ (sum of column 1). (Sum of column 3) $= 4 \times$ (sum of column 2). (Sum of row $2) = 6 +$ (sum of row $1$). (Sum of row $3) = 6 +$ (sum of row 2).
Statements
(9) The sum of all the entries in $M$ must be divisible by 21. (10) None of the row sums is divisible by 7. (11) One of the column sums must be divisible by 7. (12) None of the column sums is divisible by 6.

6. Suppose that $A$ is an $n \times n$ matrix with $n \geq 6$. For an $n \times 1$ vector $b$ consider the equations
$$\begin{aligned} & A x = b , \text { for an } n \times 1 \text { vector } x \\ & A ^ { T } x = b \text { for an } n \times 1 \text { vector } x \end{aligned}$$
where $A ^ { T }$ is the transpose of the matrix $A$. Which of the following statements are correct?
(a) If equation (??) admits a solution for all $b$, then $A ^ { - 1 }$ exists.
(b) If equation (??) admits a solution for all $b$, then equation (??) also admits a solution for all $b$.
(c) If equation (??) admits a solution for some $b$, then $A ^ { - 1 }$ exists.
(d) If equation (??) admits a solution for some $b$, then equation (??) also admits a solution for that $b$.

8. Which of the following statements are valid for all $n \times n$ matrices $A , B$ :
(a) $\left( A ^ { T } A \right) ^ { T } = A A ^ { T }$.
(b) If $A , B$ are invertible, then inverse of $A B$ is $A ^ { - 1 } B ^ { - 1 }$.
(c) $( A + B ) ^ { T } = A ^ { T } + B ^ { T }$
(d) $A x = B x$ for some $n \times 1$ vector $x$ implies that $A y = B y$ for all $n \times 1$ vectors $y$.