We prove Broyden's theorem by induction on the dimension. We assume the result holds up to rank $n - 1$ and we write $O$ in the form of a block matrix $$O = \left( \begin{array} { l l } P & r \\ { } ^ { t } q & \alpha \end{array} \right)$$ where $P \in M _ { n - 1 } ( \mathbb { R } )$ and thus $r , q \in \mathbb { R } ^ { n - 1 }$ and $\alpha \in \mathbb { R }$.
Show that $| \alpha | \leq 1$ with equality if and only if $q = r = 0$.

a) For any matrix $M \in M _ { n } ( \mathbb { C } )$ and any real number $C > 0$, show the equivalence $$\| M \| \leqslant C \Longleftrightarrow \forall x \in \mathbb { C } ^ { n } : \| M x \| _ { 1 } \leqslant C \| x \| _ { 1 } .$$ b) Show that the map $M \longmapsto \| M \|$ is a norm on $M _ { n } ( \mathbb { C } )$.

Show that for $A , B \in M _ { n } ( \mathbb { C } ) , \| A B \| \leqslant \| A \| \| B \|$.

Let $A \in M _ { n } ( \mathbb { C } )$. We denote by $a _ { i , j }$ the coefficient of $A$ with row index $i$ and column index $j$. Show that $$\| A \| = \max _ { 1 \leqslant j \leqslant n } \left( \sum _ { i = 1 } ^ { n } \left| a _ { i , j } \right| \right)$$

We say that a sequence $\left( A ^ { ( k ) } \right) _ { k \in \mathbb { N } }$ of matrices in $M _ { n } ( \mathbb { C } )$ converges to a matrix $B \in M _ { n } ( \mathbb { C } )$ when $$\forall i \in \llbracket 1 , n \rrbracket , \forall j \in \llbracket 1 , n \rrbracket , \lim _ { k \rightarrow + \infty } \left( a _ { i , j } \right) ^ { ( k ) } = b _ { i , j }$$ Show that the sequence $( A ^ { ( k ) } )$ converges to $B$ if and only if $\lim _ { k \rightarrow + \infty } \left\| A ^ { ( k ) } - B \right\| = 0$.

We consider in this question a matrix $A \in M _ { n } ( \mathbb { C } )$ that is upper triangular, $$A = \left( \begin{array} { c c c c c } a _ { 1,1 } & a _ { 1,2 } & \ldots & \ldots & a _ { 1 , n } \\ 0 & a _ { 2,2 } & \ldots & \ldots & a _ { 2 , n } \\ \vdots & \ddots & \ddots & & \vdots \\ \vdots & & \ddots & \ddots & \vdots \\ 0 & \ldots & \ldots & 0 & a _ { n , n } \end{array} \right)$$ We assume that $$\forall i \in \llbracket 1 , n \rrbracket , \left| a _ { i , i } \right| < 1$$ For any real $b > 0$, we set $P _ { b } = \operatorname { diag } \left( 1 , b , b ^ { 2 } , \ldots , b ^ { n - 1 } \right) \in M _ { n } ( \mathbb { R } )$. a) Compute $P _ { b } ^ { - 1 } A P _ { b }$. What happens when $b$ tends to 0? b) Show that there exists $b > 0$ such that $$\left\| P _ { b } ^ { - 1 } A P _ { b } \right\| < 1$$ c) Deduce that the sequence $\left( A ^ { k } \right) _ { k \in \mathbb { N } ^ { * } }$ converges to 0.

Show that for any matrix $A \in M _ { n } ( \mathbb { C } )$, $$\rho ( A ) \leqslant \| A \| .$$

Let $A \in M _ { n } ( \mathbb { C } )$. Show that if $\rho ( A ) < 1$, then the sequence $\left( A ^ { k } \right) _ { k \in \mathbb { N } ^ { * } }$ converges to 0.

Let $A \in M _ { n } ( \mathbb { C } )$. a) Show that, for all $k \in \mathbb { N } ^ { * } , \left\| A ^ { k } \right\| \geqslant \rho ( A ) ^ { k }$. b) We define the subset of $\mathbb { R } _ { + }$ $$E _ { A } = \left\{ \alpha > 0 \left\lvert \, \lim _ { k \rightarrow + \infty } \left( \frac { A } { \alpha } \right) ^ { k } = 0 \right. \right\} .$$ Show that $\left. E _ { A } = \right] \rho ( A ) , + \infty [$.

Let $A \in M _ { n } ( \mathbb { C } )$. Show the formula $$\lim _ { k \rightarrow + \infty } \left\| A ^ { k } \right\| ^ { 1 / k } = \rho ( A )$$

For $A \in M _ { n } ( \mathbb { C } )$ with coefficients $a _ { i , j }$, we set $A _ { + } = \left( b _ { i , j } \right) _ { 1 \leqslant i , j \leqslant n }$, where $b _ { i , j } = \left| a _ { i , j } \right|$. Show the inequality $$\rho ( A ) \leqslant \rho \left( A _ { + } \right)$$

Throughout this part, $A$ is a strictly positive matrix in $M _ { n } ( \mathbb { R } )$. Suppose that there exist a non-negative real $\mu$ and a positive non-zero vector $w$ such that $A w \geqslant \mu w$. a) Show that for all natural integer $k , A ^ { k } w \geqslant \mu ^ { k } w$. Deduce that $\rho ( A ) \geqslant \mu$. b) Show that if $A w > \mu w$, then $\rho ( A ) > \mu$. c) We now suppose that in the system of inequalities $A w \geqslant \mu w$, the $k$-th inequality is strict, that is $$\sum _ { j = 1 } ^ { n } a _ { k j } w _ { j } > \mu w _ { k } .$$ Show that there exists $\epsilon > 0$ such that, by setting $w _ { j } ^ { \prime } = w _ { j }$ if $j \neq k$ and $w _ { k } ^ { \prime } = w _ { k } + \epsilon$, we have $A w ^ { \prime } > \mu w ^ { \prime }$. Deduce that $\rho ( A ) > \mu$.

Verify the following property: $\forall ( A , B ) \in \left( \mathcal { M } _ { n } ( \mathbb { C } ) \right) ^ { 2 } \quad \| A B \| _ { 0 } \leqslant n \| A \| _ { 0 } \cdot \| B \| _ { 0 }$

Verify the following property: $\forall A \in \mathcal { M } _ { n } ( \mathbb { C } ) , \forall Y \in \mathbb { C } ^ { n } \quad \| A Y \| _ { \infty } \leqslant n \| A \| _ { 0 } \cdot \| Y \| _ { \infty }$

Let $n$ and $p$ be two integers greater than or equal to 2. We fix a sequence $\left( A _ { k } \right) _ { k \in \mathbb { N } }$ of matrices of $\mathrm { GL } _ { n } ( \mathbb { C } )$ which is $p$-periodic. The sequence $\left( \Phi _ { k } \right) _ { k \in \mathbb { N } }$ is defined by $\Phi _ { 0 } = I _ { n }$ and $\Phi _ { k + 1 } = A _ { k } \Phi _ { k }$. We denote by $B$ a matrix in $\mathrm { GL } _ { n } ( \mathbb { C } )$ satisfying $B ^ { p } = \Phi _ { p }$, and $\left( P _ { k } \right) _ { k \in \mathbb { N } }$ the unique $p$-periodic sequence in $\left( \mathrm { GL } _ { n } ( \mathbb { C } ) \right) ^ { \mathbb { N } }$ such that $\Phi _ { k } = P _ { k } B ^ { k }$ for all $k \in \mathbb{N}$. Let $\left( Y _ { k } \right) _ { k \in \mathbb { N } }$ be a solution of (III.1). Justify the existence of $M = \max _ { k \in \mathbb { N } } \left\| P _ { k } \right\| _ { 0 }$. Show that for all $k \in \mathbb { N } , \left\| \Phi _ { k } \right\| _ { 0 } \leqslant n M \left\| B ^ { k } \right\| _ { 0 }$.

Let $n$ and $p$ be two integers greater than or equal to 2. We fix a sequence $\left( A _ { k } \right) _ { k \in \mathbb { N } }$ of matrices of $\mathrm { GL } _ { n } ( \mathbb { C } )$ which is $p$-periodic. The sequence $\left( \Phi _ { k } \right) _ { k \in \mathbb { N } }$ is defined by $\Phi _ { 0 } = I _ { n }$ and $\Phi _ { k + 1 } = A _ { k } \Phi _ { k }$. We denote by $B$ a matrix in $\mathrm { GL } _ { n } ( \mathbb { C } )$ satisfying $B ^ { p } = \Phi _ { p }$, and $\left( P _ { k } \right) _ { k \in \mathbb { N } }$ the unique $p$-periodic sequence such that $\Phi _ { k } = P _ { k } B ^ { k }$. Let $\left( Y _ { k } \right) _ { k \in \mathbb { N } }$ be a solution of (III.1).
a) Prove that if $\lim _ { k \rightarrow + \infty } \left\| B ^ { k } \right\| _ { 0 } = 0$, then $\lim _ { k \rightarrow + \infty } \left\| Y _ { k } \right\| _ { \infty } = 0$.
b) Prove that if the sequence $\left( \left\| B ^ { k } \right\| _ { 0 } \right) _ { k \in \mathbb { N } }$ is bounded, then the sequence $\left( \left\| Y _ { k } \right\| _ { \infty } \right) _ { k \in \mathbb { N } }$ is also bounded.

With $A = (1-2r)I_{q} + rB$, $r = \frac{\tau}{\delta^2}$, $\delta = \frac{1}{q+1}$, give a necessary and sufficient condition on $r$ for the sequence $\left(F_{n}\right)_{n \in \mathbb{N}}$ to be bounded regardless of the choices of $q$ and $F_{0}$.

We denote by $\mathbb{R}_{N}[X]$ the vector space of polynomials with real coefficients, of degree at most $N$. We define the set $A_{N}$ formed by $P \in \mathbb{R}_{N}[X]$, such that $P(-1) = P(1) = 1$, which furthermore satisfy $P(x) \geqslant 0$ for all $x$ in the interval $[-1,1]$. We define on $\mathbb{R}_{N}[X]$ a linear form $L$ by $L(P) = \int_{-1}^{1} P(x)\,dx$.
(a) Verify that $A_{N}$ is a convex subset of $\mathbb{R}_{N}[X]$.
(b) Show that the expression $$\|P\|_{1} = \int_{-1}^{1} |P(x)|\,dx$$ defines a norm on $\mathbb{R}_{N}[X]$.
(c) Show that $A_{N}$ is closed in the normed vector space $\left(\mathbb{R}_{N}[X], \|\cdot\|_{1}\right)$.

We fix $A \in \mathcal{M}_{n}(\{-1,1\})$ and denote $$m(A) := \min(S(A) \cap \mathbb{N}).$$
For $Y \in \{-1,1\}^{n}$, show that we have $$\min\left\{\left|{}^{t}X A Y\right| \mid X \in \{-1,1\}^{n}\right\} \leqslant n$$ and deduce $m(A) \leqslant n$.

Let $n \in \mathbb { N } ^ { * }$. We define the map $N$ from $\mathcal { M } _ { n } ( \mathbb { R } )$ to $\mathbb { R }$ by the relation:
$$N ( A ) = \sup \left\{ \| A x \| _ { \infty } , \| x \| _ { \infty } \leq 1 \right\}$$
Show that $N$ is a norm on $\mathcal { M } _ { n } ( \mathbb { R } )$ and that if $A = \left[ a _ { i , j } \right] _ { 1 \leq i , j \leq n }$, then
$$N ( A ) = \max _ { i \in \{ 1 , \ldots , n \} } \sum _ { j = 1 } ^ { n } \left| a _ { i , j } \right|$$

Let $n \in \mathbb { N } ^ { * }$.
(a) Using the results of questions 14 and 15, show that for the matrix $A _ { n }$ defined at the beginning of part 2, we have:
$$N \left( \left( ( n + 1 ) ^ { 2 } A _ { n } \right) ^ { - 1 } \right) \leq \frac { 1 } { 8 }$$
(b) Deduce that for any diagonal matrix $D _ { n } = \left[ d _ { i , j } \right] _ { 1 \leq i , j \leq n }$ such that $d _ { i , i } \geq 0$ for all $i \in \{ 1 , \ldots , n \}$, we also have
$$N \left( \left( ( n + 1 ) ^ { 2 } A _ { n } + D _ { n } \right) ^ { - 1 } \right) \leq \frac { 1 } { 8 }$$

Let $u$ be the unique solution of problem (1) and $\left( u _ { i } \right) _ { 0 \leq i \leq n + 1 }$ the family defined by relation (2) for $n \in \mathbb { N } ^ { * }$. Show that there exists a constant $\tilde { C } > 0$, independent of $n$, such that
$$\max _ { 0 \leq i \leq n + 1 } \left| u \left( x _ { i } \right) - u _ { i } \right| \leq \frac { \tilde { C } } { n ^ { 2 } }$$
Hint: one may introduce the vector $X = {}^{ t } \left( \varepsilon _ { 1 } , \ldots , \varepsilon _ { n } \right)$ where we set $\varepsilon _ { i } = u \left( x _ { i } \right) - u _ { i }$ and compute $A _ { n } X$.

Let $a$ and $b$ be in $E$. Show the following relation and give a geometric interpretation:
$$\|a + b\|^{2} + \|a - b\|^{2} = 2(\|a\|^{2} + \|b\|^{2})$$

We consider the space $E = \mathcal{M}_{k,d}(\mathbb{R})$ equipped with the inner product defined by
$$\forall (A, B) \in E^{2}, \quad \langle A \mid B \rangle = \operatorname{tr}\left(A^{\top} \cdot B\right)$$
We denote by $\|\cdot\|_{F}$ the associated Euclidean norm. We fix a unit vector $u$ in $\mathbb{R}^{d}$ and define $g(M) = \|M \cdot u\|$. Show that for every matrix $M$ in $\mathcal{M}_{k,d}(\mathbb{R})$
$$\|M \cdot u\| \leqslant \|M\|_{F}$$

Let $a$ and $b$ be in $E$. Show the following relation and give a geometric interpretation:
$$\|a + b\|^{2} + \|a - b\|^{2} = 2(\|a\|^{2} + \|b\|^{2})$$