grandes-ecoles

Papers (191)

2025

centrale-maths1__official 40 centrale-maths2__official 42 mines-ponts-maths1__mp 20 mines-ponts-maths1__pc 21 mines-ponts-maths1__psi 21 mines-ponts-maths2__mp 28 mines-ponts-maths2__pc 24 mines-ponts-maths2__psi 26 polytechnique-maths-a__mp 27 polytechnique-maths__fui 16 polytechnique-maths__pc 27 x-ens-maths-a__mp 18 x-ens-maths-c__mp 9 x-ens-maths-d__mp 38 x-ens-maths__pc 27 x-ens-maths__psi 38

2024

centrale-maths1__official 28 centrale-maths2__official 29 geipi-polytech__maths 9 mines-ponts-maths1__mp 25 mines-ponts-maths1__pc 20 mines-ponts-maths1__psi 19 mines-ponts-maths2__mp 23 mines-ponts-maths2__pc 21 mines-ponts-maths2__psi 21 polytechnique-maths-a__mp 44 polytechnique-maths-b__mp 37 x-ens-maths-a__mp 43 x-ens-maths-b__mp 35 x-ens-maths-c__mp 22 x-ens-maths-d__mp 45 x-ens-maths__pc 24 x-ens-maths__psi 26

2023

centrale-maths1__official 44 centrale-maths2__official 33 e3a-polytech-maths__mp 4 mines-ponts-maths1__mp 15 mines-ponts-maths1__pc 23 mines-ponts-maths1__psi 23 mines-ponts-maths2__mp 22 mines-ponts-maths2__pc 18 mines-ponts-maths2__psi 22 polytechnique-maths__fui 23 x-ens-maths-a__mp 25 x-ens-maths-b__mp 24 x-ens-maths-c__mp 20 x-ens-maths-d__mp 20 x-ens-maths__pc 18 x-ens-maths__psi 15

2022

centrale-maths1__mp 48 centrale-maths1__official 48 centrale-maths1__pc 37 centrale-maths1__psi 43 centrale-maths2__mp 32 centrale-maths2__official 32 centrale-maths2__pc 39 centrale-maths2__psi 45 mines-ponts-maths1__mp 25 mines-ponts-maths1__pc 24 mines-ponts-maths1__psi 24 mines-ponts-maths2__mp 24 mines-ponts-maths2__pc 19 mines-ponts-maths2__psi 20 x-ens-maths-a__mp 13 x-ens-maths-b__mp 40 x-ens-maths-c__mp 27 x-ens-maths-d__mp 46 x-ens-maths1__mp 13 x-ens-maths2__mp 40 x-ens-maths__pc 15 x-ens-maths__pc_cpge 15 x-ens-maths__psi 22 x-ens-maths__psi_cpge 23

2021

centrale-maths1__mp 40 centrale-maths1__official 40 centrale-maths1__pc 36 centrale-maths1__psi 29 centrale-maths2__mp 30 centrale-maths2__official 29 centrale-maths2__pc 38 centrale-maths2__psi 37 x-ens-maths2__mp 39 x-ens-maths__pc 44

2020

centrale-maths1__mp 42 centrale-maths1__official 42 centrale-maths1__pc 36 centrale-maths1__psi 40 centrale-maths2__mp 38 centrale-maths2__official 38 centrale-maths2__pc 40 centrale-maths2__psi 39 mines-ponts-maths1__mp_cpge 24 mines-ponts-maths2__mp_cpge 21 x-ens-maths-a__mp_cpge 18 x-ens-maths-b__mp_cpge 20 x-ens-maths-d__mp 14 x-ens-maths1__mp 18 x-ens-maths2__mp 20 x-ens-maths__pc 18

2019

centrale-maths1__mp 37 centrale-maths1__official 37 centrale-maths1__pc 40 centrale-maths1__psi 39 centrale-maths2__mp 37 centrale-maths2__official 37 centrale-maths2__pc 39 centrale-maths2__psi 49 x-ens-maths1__mp 24 x-ens-maths__pc 18 x-ens-maths__psi 26

2018

centrale-maths1__mp 47 centrale-maths1__official 47 centrale-maths1__pc 41 centrale-maths1__psi 44 centrale-maths2__mp 44 centrale-maths2__official 44 centrale-maths2__pc 35 centrale-maths2__psi 38 x-ens-maths1__mp 19 x-ens-maths2__mp 17 x-ens-maths__pc 22 x-ens-maths__psi 24

2017

centrale-maths1__mp 45 centrale-maths1__official 45 centrale-maths1__pc 22 centrale-maths1__psi 17 centrale-maths2__mp 30 centrale-maths2__official 30 centrale-maths2__pc 28 centrale-maths2__psi 44 x-ens-maths1__mp 26 x-ens-maths2__mp 16 x-ens-maths__pc 18 x-ens-maths__psi 26

2016

centrale-maths1__mp 42 centrale-maths1__pc 31 centrale-maths1__psi 33 centrale-maths2__mp 25 centrale-maths2__pc 47 centrale-maths2__psi 27 x-ens-maths1__mp 18 x-ens-maths2__mp 46 x-ens-maths__pc 15 x-ens-maths__psi 20

2015

centrale-maths1__mp 42 centrale-maths1__pc 18 centrale-maths1__psi 42 centrale-maths2__mp 44 centrale-maths2__pc 18 centrale-maths2__psi 33 x-ens-maths1__mp 16 x-ens-maths2__mp 31 x-ens-maths__pc 30 x-ens-maths__psi 22

2014

centrale-maths1__mp 28 centrale-maths1__pc 26 centrale-maths1__psi 27 centrale-maths2__mp 24 centrale-maths2__pc 26 centrale-maths2__psi 27 x-ens-maths1__mp 9 x-ens-maths2__mp 16 x-ens-maths__pc 4 x-ens-maths__psi 24

2013

centrale-maths1__mp 22 centrale-maths1__pc 45 centrale-maths1__psi 29 centrale-maths2__mp 31 centrale-maths2__pc 52 centrale-maths2__psi 32 x-ens-maths1__mp 24 x-ens-maths2__mp 35 x-ens-maths__pc 22 x-ens-maths__psi 9

2012

centrale-maths1__mp 36 centrale-maths1__pc 28 centrale-maths1__psi 33 centrale-maths2__mp 27 centrale-maths2__psi 18

2011

centrale-maths1__mp 27 centrale-maths1__pc 17 centrale-maths1__psi 24 centrale-maths2__mp 29 centrale-maths2__pc 17 centrale-maths2__psi 10

2010

centrale-maths1__mp 19 centrale-maths1__pc 30 centrale-maths1__psi 13 centrale-maths2__mp 32 centrale-maths2__pc 37 centrale-maths2__psi 27

2019 x-ens-maths__psi

26 maths questions

Q1 Invariant lines and eigenvalues and vectors Eigenvalue constraints from matrix properties View

Let $A \in \mathcal { S } _ { N } ( \mathbb { R } )$. Show that $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$ if and only if the eigenvalues of $A$ are all strictly positive real numbers.

Q2 Matrices Matrix Norm, Convergence, and Inequality View

For any matrix $B \in \mathcal { M } _ { N } ( \mathbb { R } )$, we set $\| B \| = \sup _ { \| x \| = 1 } \| B x \|$.
After justifying the existence of $\| B \|$, show that $B \mapsto \| B \|$ is a norm on $\mathcal { M } _ { N } ( \mathbb { R } )$ satisfying $$\forall x \in \mathbb { R } ^ { N } \quad \| B x \| \leq \| B \| \| x \|$$

Q3 Matrices Matrix Norm, Convergence, and Inequality View

Let $A \in \mathcal { S } _ { N } ( \mathbb { R } )$ be a matrix with eigenvalues (not necessarily distinct) $\lambda _ { 1 } , \ldots , \lambda _ { N }$. Show that $$\| A \| = \max _ { 1 \leq i \leq N } \left| \lambda _ { i } \right|$$

Q4 Matrices Matrix Norm, Convergence, and Inequality View

Let $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$. For all $x \in \mathbb { R } ^ { N }$, we set $\| x \| _ { A } = \langle x , A x \rangle ^ { 1 / 2 }$.
a) Show that the map $x \mapsto \| x \| _ { A }$ is a norm on $\mathbb { R } ^ { N }$.
b) Show that there exist constants $C _ { 1 }$ and $C _ { 2 }$ strictly positive, which we will express in terms of the eigenvalues of $A$, such that $$\forall x \in \mathbb { R } ^ { N } \quad C _ { 1 } \| x \| \leq \| x \| _ { A } \leq C _ { 2 } \| x \| .$$

Q5 Matrices Eigenvalue and Characteristic Polynomial Analysis View

Let $A \in \mathcal { S } _ { N } ( \mathbb { R } )$ and let $P \in \mathbb { R } [ X ]$ be a polynomial. Show that $P ( A ) \in \mathcal { S } _ { N } ( \mathbb { R } )$ and specify the eigenvalues and eigenvectors of $P ( A )$ in terms of those of $A$.

Q6 Matrices Matrix Decomposition and Factorization View

Let $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$. We denote by $0 < \lambda _ { 1 } < \cdots < \lambda _ { d }$ the $d$ eigenvalues of $A$ (distinct pairwise) and $F _ { 1 } , \ldots , F _ { d }$ the associated eigenspaces. We consider the linear map from $\mathbb { R } ^ { N }$ to $\mathbb { R } ^ { N }$: $$x \mapsto \sum _ { i = 1 } ^ { d } \lambda _ { i } ^ { 1 / 2 } p _ { F _ { i } } ( x )$$ where $p _ { F _ { i } }$ is the orthogonal projection (for the canonical inner product) onto $F _ { i }$. We denote by $A ^ { 1 / 2 }$ the matrix associated with this linear map in the canonical basis.
a) We write $A = U D U ^ { T }$, where $D \in \mathcal { M } _ { N } ( \mathbb { R } )$ is the diagonal matrix containing the eigenvalues of $A$ in increasing order, with their multiplicities, and $U$ an orthogonal matrix. We denote by $D ^ { 1 / 2 }$ the diagonal matrix whose diagonal coefficients are the square roots of those of $D$. Show that $A ^ { 1 / 2 } = U D ^ { 1 / 2 } U ^ { T }$.
b) Show that $A ^ { 1 / 2 } \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$, that $A ^ { 1 / 2 } A ^ { 1 / 2 } = A$, and that $A ^ { 1 / 2 }$ commutes with $A$.
c) Show that, for all $x \in \mathbb { R } ^ { N } , \| x \| _ { A } = \left\| A ^ { 1 / 2 } x \right\|$, where $\| x \| _ { A }$ is the norm defined in question 4.

Q7 Matrices Linear System and Inverse Existence View

Let $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$. We are given $b \in \mathbb { R } ^ { N }$ and we denote by $\tilde { x } \in \mathbb { R } ^ { N }$ the unique vector satisfying $A \tilde { x } = b$. We are given a vector $x _ { 0 } \in \mathbb { R } ^ { N }$, different from $\tilde { x }$, and we denote by $r _ { 0 } = b - A x _ { 0 }$. We set $H _ { 0 } = \{ 0 \}$ and for $k \geq 1$, $$H _ { k } = \left\{ P ( A ) r _ { 0 } \mid P \in \mathbb { R } [ X ] , \operatorname { deg } ( P ) \leq k - 1 \right\}$$ where $\operatorname { deg } ( P ) \in \mathbb { N }$ denotes the degree of the polynomial $P$.
Show that the $H _ { k }$ form a sequence of vector subspaces of $\mathbb { R } ^ { N }$, and show that $H _ { k } \subset H _ { k + 1 }$ for all $k \in \mathbb { N }$.
a) Show that there necessarily exists $k$ such that $H _ { k + 1 } = H _ { k }$. We then denote by $m$ the smallest integer $k$ such that $H _ { k + 1 } = H _ { k }$.
b) Show that $\operatorname { dim } \left( H _ { k } \right) = m$ for all $k \geq m$, and that $\operatorname { dim } \left( H _ { k } \right) = k$ for $k \leq m$.

Q8 Matrices Eigenvalue and Characteristic Polynomial Analysis View

Let $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$. We are given $b \in \mathbb { R } ^ { N }$ and we denote by $\tilde { x } \in \mathbb { R } ^ { N }$ the unique vector satisfying $A \tilde { x } = b$. We are given a vector $x _ { 0 } \in \mathbb { R } ^ { N }$, different from $\tilde { x }$, and we denote by $r _ { 0 } = b - A x _ { 0 }$. We set $H _ { 0 } = \{ 0 \}$ and for $k \geq 1$, $$H _ { k } = \left\{ P ( A ) r _ { 0 } \mid P \in \mathbb { R } [ X ] , \operatorname { deg } ( P ) \leq k - 1 \right\}$$ We denote by $m$ the smallest integer $k$ such that $H _ { k + 1 } = H _ { k }$. We denote by $d$ the number of distinct eigenvalues of $A$.
a) In the special case where $r _ { 0 }$ is an eigenvector of $A$, show that the integer $m$ is equal to 1.
b) In the general case, show that $m$ is less than or equal to $d$.
c) For any integer $n$ between 1 and $d$, construct an $x _ { 0 }$ such that the integer $m$ is equal to $n$.
d) Show that the set of $x _ { 0 }$ for which the dimension $m$ is exactly equal to $d$ is the complement of a finite union of sets of the form $\tilde { x } + E$, where $E$ is a vector space of dimension less than or equal to $N - 1$.

Q9 Matrices Eigenvalue and Characteristic Polynomial Analysis View

Q10 Matrices Eigenvalue and Characteristic Polynomial Analysis View

Q11 Matrices Linear System and Inverse Existence View

Let $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$. We are given $b \in \mathbb { R } ^ { N }$ and we denote by $\tilde { x } \in \mathbb { R } ^ { N }$ the unique vector satisfying $A \tilde { x } = b$. We are given a vector $x _ { 0 } \in \mathbb { R } ^ { N }$, different from $\tilde { x }$, and we denote by $r _ { 0 } = b - A x _ { 0 }$. We set $H _ { 0 } = \{ 0 \}$ and for $k \geq 1$, $$H _ { k } = \left\{ P ( A ) r _ { 0 } \mid P \in \mathbb { R } [ X ] , \operatorname { deg } ( P ) \leq k - 1 \right\}$$ We denote by $m$ the smallest integer $k$ such that $H _ { k + 1 } = H _ { k }$. We define $x _ { 0 } + H _ { k }$ as the subset of points of $\mathbb { R } ^ { N }$ of the form $x _ { 0 } + x$ where $x$ ranges over the vector space $H _ { k }$.
a) Show that $\tilde { x } \in x _ { 0 } + H _ { m }$.
b) Show that, for all $k \in \{ 0 , \ldots , m - 1 \}$, we have $\tilde { x } \notin x _ { 0 } + H _ { k }$.

Q12 Matrices Linear System and Inverse Existence View

We introduce the map $$\begin{aligned} J : \mathbb { R } ^ { N } & \rightarrow \mathbb { R } \\ x & \mapsto \frac { 1 } { 2 } \langle x , A x \rangle - \langle b , x \rangle \end{aligned}$$ where $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$, $b \in \mathbb { R } ^ { N }$, and $\tilde { x }$ is the unique vector satisfying $A \tilde { x } = b$.
For all $x \in \mathbb { R } ^ { N }$, express $\| x - \tilde { x } \| _ { A } ^ { 2 } = \langle x - \tilde { x } , A ( x - \tilde { x } ) \rangle$ in terms of $J ( \tilde { x } )$ and $J ( x )$ and deduce that $\tilde { x }$ is the unique minimizer of $J$ on $\mathbb { R } ^ { N }$, that is, $J ( \tilde { x } ) \leq J ( x )$ for all $x \in \mathbb { R } ^ { N }$, and that $\tilde { x }$ is the only point satisfying this property.

Q13 Matrices Linear System and Inverse Existence View

We introduce the map $$\begin{aligned} J : \mathbb { R } ^ { N } & \rightarrow \mathbb { R } \\ x & \mapsto \frac { 1 } { 2 } \langle x , A x \rangle - \langle b , x \rangle \end{aligned}$$ where $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$, $b \in \mathbb { R } ^ { N }$. We set $H _ { 0 } = \{ 0 \}$ and for $k \geq 1$, $$H _ { k } = \left\{ P ( A ) r _ { 0 } \mid P \in \mathbb { R } [ X ] , \operatorname { deg } ( P ) \leq k - 1 \right\}$$ and $x _ { 0 } + H _ { k }$ denotes the subset of points of $\mathbb { R } ^ { N }$ of the form $x _ { 0 } + x$ where $x$ ranges over $H _ { k }$.
Show that $J$ admits a unique minimizer on the subset $x _ { 0 } + H _ { k }$, for any $k \in \mathbb { N }$.

Q14 Matrices Projection and Orthogonality View

We introduce the map $$\begin{aligned} J : \mathbb { R } ^ { N } & \rightarrow \mathbb { R } \\ x & \mapsto \frac { 1 } { 2 } \langle x , A x \rangle - \langle b , x \rangle \end{aligned}$$ where $A \in \mathcal { S } _ { N } ^ { + } ( \mathbb { R } )$, $b \in \mathbb { R } ^ { N }$, and $\tilde { x }$ is the unique vector satisfying $A \tilde { x } = b$. We denote by $x _ { k }$ the minimizer of $J$ on $x _ { 0 } + H _ { k }$.
Show that $x _ { k }$ identifies with the projection onto $x _ { 0 } + H _ { k }$ for the norm $\| \cdot \| _ { A }$ associated with the matrix $A$, that is, $$\left\| x _ { k } - \tilde { x } \right\| _ { A } = \min _ { x \in x _ { 0 } + H _ { k } } \| x - \tilde { x } \| _ { A }$$

Q15 Matrices Matrix Power Computation and Application View

We keep the notations from Parts II and III. We denote $r _ { k } = b - A x _ { k }$, $e _ { k } = x _ { k } - \tilde { x }$, and note that $r _ { k } = - A e _ { k }$. We denote by $m$ the smallest integer $k$ such that $H _ { k + 1 } = H _ { k }$.
Show that $e _ { k } \neq 0$ for $k \in \{ 0 , \ldots , m - 1 \}$, and that $e _ { k } = 0$ for $k \geq m$.

Q16 Matrices Matrix Norm, Convergence, and Inequality View

We keep the notations from Parts II and III. We denote $e _ { k } = x _ { k } - \tilde { x }$ and $e _ { 0 } = x _ { 0 } - \tilde { x }$. We recall that $I _ { N }$ is the identity matrix of order $N$.
Show that $$\left\| e _ { k } \right\| _ { A } = \min \left\{ \left\| \left( I _ { N } + A Q ( A ) \right) e _ { 0 } \right\| _ { A } \mid Q \in \mathbb { R } [ X ] , \operatorname { deg } ( Q ) \leq k - 1 \right\}$$

Q17 Matrices Matrix Norm, Convergence, and Inequality View

We keep the notations from Parts II and III. We denote $e _ { k } = x _ { k } - \tilde { x }$ and $e _ { 0 } = x _ { 0 } - \tilde { x }$. We recall that $I _ { N }$ is the identity matrix of order $N$, and $\| \cdot \|$ denotes the matrix norm defined in question 2.
Show that $$\left\| e _ { k } \right\| _ { A } \leq \left\| e _ { 0 } \right\| _ { A } \min \left\{ \left\| I _ { N } + A Q ( A ) \right\| \mid Q \in \mathbb { R } [ X ] , \operatorname { deg } ( Q ) \leq k - 1 \right\}$$ (One may use the properties of $A ^ { 1 / 2 }$ demonstrated in question 6.)

Q18 Matrices Matrix Norm, Convergence, and Inequality View

We denote by $\lambda _ { 1 }$ (respectively $\lambda _ { N }$) the smallest (respectively largest) eigenvalue of $A$, and we define $$\Lambda _ { k } = \{ Q \in \mathbb { R } [ X ] \mid \operatorname { deg } ( Q ) \leq k , Q ( 0 ) = 1 \}$$
Show that $$\left\| e _ { k } \right\| _ { A } \leq \left\| e _ { 0 } \right\| _ { A } \min _ { Q \in \Lambda _ { k } } \max _ { t \in \left[ \lambda _ { 1 } , \lambda _ { N } \right] } | Q ( t ) |$$

Q19 Sequences and Series Recurrence Relations and Sequence Properties View

Let $k$ be a non-negative integer. We define the function $f _ { k }$ from the interval $[ - 1,1 ]$ to itself by $f _ { k } ( x ) = \cos ( k \arccos x )$.
a) Expand the expression $f _ { k + 1 } ( x ) + f _ { k - 1 } ( x )$, and deduce the relation $$\forall x \in [ - 1,1 ] \quad f _ { k + 1 } ( x ) = 2 x f _ { k } ( x ) - f _ { k - 1 } ( x )$$
b) Deduce that $f _ { k }$ identifies on $[ - 1,1 ]$ with a polynomial $T _ { k }$, of degree $k$, with the same parity as $k$.

Q20 Hyperbolic functions View

Let $k$ be a non-negative integer. We define the function $f _ { k }$ from the interval $[ - 1,1 ]$ to itself by $f _ { k } ( x ) = \cos ( k \arccos x )$, and $T_k$ is the polynomial of degree $k$ that identifies with $f_k$ on $[-1,1]$. We denote by arcosh the inverse function of the hyperbolic cosine, defined from $[ 1 , + \infty [$ to $[ 0 , + \infty [$.
Show that $$\forall x \in ] - \infty , - 1 ] \quad T _ { k } ( x ) = ( - 1 ) ^ { k } \cosh ( k \operatorname { arcosh } ( - x ) ) .$$

Q21 Hyperbolic functions View

Let $k$ be a non-negative integer. We define the function $f _ { k }$ from the interval $[ - 1,1 ]$ to itself by $f _ { k } ( x ) = \cos ( k \arccos x )$, and $T_k$ is the polynomial of degree $k$ that identifies with $f_k$ on $[-1,1]$. We recall that $A \in \mathcal{S}_N^+(\mathbb{R})$ is not proportional to the identity, $\lambda_1$ is the smallest eigenvalue of $A$, $\lambda_N$ is the largest eigenvalue of $A$, and $$\Lambda _ { k } = \{ Q \in \mathbb { R } [ X ] \mid \operatorname { deg } ( Q ) \leq k , Q ( 0 ) = 1 \}$$
We set $\omega _ { k } = \frac { 1 } { T _ { k } \left( - \frac { \lambda _ { N } + \lambda _ { 1 } } { \lambda _ { N } - \lambda _ { 1 } } \right) }$. Show that $\omega _ { k }$ is well defined, that the polynomial $$Q _ { k } ( X ) = \omega _ { k } T _ { k } \left( \frac { 2 X - \lambda _ { 1 } - \lambda _ { N } } { \lambda _ { N } - \lambda _ { 1 } } \right)$$ is an element of $\Lambda _ { k }$, and that the maximum of $| Q _ { k } ( t ) |$ on $\left[ \lambda _ { 1 } , \lambda _ { N } \right]$ is $\left| \omega _ { k } \right|$.

Q22 Hyperbolic functions View

We set $\theta = \operatorname { arcosh } \left( \frac { \lambda _ { N } + \lambda _ { 1 } } { \lambda _ { N } - \lambda _ { 1 } } \right) > 0$ and $\alpha = e ^ { - \theta }$. Show that $\alpha$ is a root of the polynomial $$X ^ { 2 } - 2 \frac { \lambda _ { N } + \lambda _ { 1 } } { \lambda _ { N } - \lambda _ { 1 } } X + 1$$ and deduce the expression of $\alpha$ in terms of the quantity $\beta = \frac { \lambda _ { N } + \lambda _ { 1 } } { \lambda _ { N } - \lambda _ { 1 } }$.

Q23 Matrices Matrix Norm, Convergence, and Inequality View

We denote by $\kappa = \lambda _ { N } / \lambda _ { 1 }$. Show that the real number $\alpha$ from question 22 equals $\alpha = \frac { \sqrt { \kappa } - 1 } { \sqrt { \kappa } + 1 }$ and deduce that $$\left\| e _ { k } \right\| _ { A } \leq 2 \left\| e _ { 0 } \right\| _ { A } \left( \frac { \sqrt { \kappa } - 1 } { \sqrt { \kappa } + 1 } \right) ^ { k }$$

Q24 Matrices Projection and Orthogonality View

We keep the notations from the previous parts. In particular, we still denote by $x _ { k }$ the minimizer of $J$ on $x _ { 0 } + H _ { k }$. We set $H _ { 0 } = \{ 0 \}$ and for $k \geq 1$, $$H _ { k } = \left\{ P ( A ) r _ { 0 } \mid P \in \mathbb { R } [ X ] , \operatorname { deg } ( P ) \leq k - 1 \right\}$$
Show that there exists a family $\left( p _ { 0 } , \ldots , p _ { m - 1 } \right)$ of vectors in $\mathbb { R } ^ { N }$ such that
(i) For all $k \in \{ 1 , \ldots , m \}$, the family $( p _ { 0 } , \ldots , p _ { k - 1 } )$ is a basis of $H _ { k }$.
(ii) The family is orthogonal with respect to the inner product associated with $A$, that is $$\forall i , j \in \{ 0 , \ldots , m - 1 \} \quad i \neq j \Rightarrow \left\langle A p _ { i } , p _ { j } \right\rangle = 0$$

Q25 Matrices Projection and Orthogonality View

We keep the notations from the previous parts. In particular, we still denote by $x _ { k }$ the minimizer of $J$ on $x _ { 0 } + H _ { k }$.
Assume that a family $\left( p _ { 0 } , \ldots , p _ { m - 1 } \right)$ of vectors satisfying the properties of question 24 is known. Show that $x _ { k + 1 } - x _ { k }$ is then collinear with $p _ { k }$ for all integer $k \in \{ 0 , \ldots , m - 1 \}$.

Q26 Proof Direct Proof of a Stated Identity or Equality View

We are given $x _ { 0 } \in \mathbb { R } ^ { N }$. We consider the finite real sequences $\left( \alpha _ { k } \right)$ and $\left( \beta _ { k } \right)$, as well as the finite sequences $\left( \tilde { x } _ { k } \right) , \left( \tilde { r } _ { k } \right)$ and $\left( \tilde { p } _ { k } \right)$ of elements of $\mathbb { R } ^ { N }$, constructed according to the following recurrence relations, for $k \in \{ 0 , \ldots , m - 1 \}$, $$\begin{aligned} \alpha _ { k } & = \frac { \left\| \tilde { r } _ { k } \right\| ^ { 2 } } { \left\langle A \tilde { p } _ { k } , \tilde { p } _ { k } \right\rangle } \\ \tilde { x } _ { k + 1 } & = \tilde { x } _ { k } + \alpha _ { k } \tilde { p } _ { k } \\ \tilde { r } _ { k + 1 } & = \tilde { r } _ { k } - \alpha _ { k } A \tilde { p } _ { k } \\ \beta _ { k } & = \frac { \left\| \tilde { r } _ { k + 1 } \right\| ^ { 2 } } { \left\| \tilde { r } _ { k } \right\| ^ { 2 } } \\ \tilde { p } _ { k + 1 } & = \tilde { r } _ { k + 1 } + \beta _ { k } \tilde { p } _ { k } \end{aligned}$$ with $\tilde { x } _ { 0 } = x _ { 0 } , \tilde { r } _ { 0 } = b - A x _ { 0 }$ and $\tilde { p } _ { 0 } = \tilde { r } _ { 0 }$.
Show that the following properties are satisfied:
(i) For all $k \in \{ 0 , \ldots , m - 1 \}$, for all $i \in \{ 0 , \ldots , k - 1 \}$, we have $$\left\langle \tilde { r } _ { i } , \tilde { r } _ { k } \right\rangle = 0 , \left\langle \tilde { p } _ { i } , \tilde { r } _ { k } \right\rangle = 0 , \left\langle \tilde { p } _ { i } , A \tilde { p } _ { k } \right\rangle = 0$$
(ii) For all $k \in \{ 0 , \ldots , m \} , \tilde { x } _ { k }$ is identified with $x _ { k }$, the minimizer of $J$ on $x _ { 0 } + H _ { k }$ defined in question 13.
(iii) For all $k \in \{ 0 , \ldots , m \} , \tilde { r } _ { k }$ is identified with $r _ { k } = b - A x _ { k }$.
(iv) The family $\left( \tilde { p } _ { 0 } , \ldots , \tilde { p } _ { k } \right)$ is a basis of $H _ { k + 1 }$, for all $k \in \{ 0 , \ldots , m - 1 \}$.