We prove Broyden's theorem by induction on the dimension. We assume $| \alpha | < 1$ and we introduce the matrices $$Q _ { - } = P - \frac { r { } ^ { t } q } { \alpha - 1 } , \quad Q _ { + } = P - \frac { r { } ^ { t } q } { \alpha + 1 }$$ Using the induction hypothesis for $Q _ { + }$ (resp. for $Q _ { - }$), we denote by $x _ { + } > 0$ (resp. $x _ { - } > 0$) a vector of $\mathbb { R } ^ { n - 1 }$ and $S _ { + }$ (resp. $S _ { - }$) the sign diagonal matrix, such that $$Q _ { + } x _ { + } = S _ { + } x _ { + } , \quad \text { resp. } \quad Q _ { - } x _ { - } = S _ { - } x _ { - }$$
Show that $$\left( S _ { + } x _ { + } \mid S _ { - } x _ { - } \right) = \left( x _ { + } \mid x _ { - } \right) - \frac { 2 } { 1 - \alpha ^ { 2 } } \left( x _ { + } \mid q \right) \left( x _ { - } \mid q \right)$$

We prove Broyden's theorem by induction on the dimension. We assume $| \alpha | < 1$. Using the induction hypothesis for $Q _ { + }$ (resp. for $Q _ { - }$), we denote by $x _ { + } > 0$ (resp. $x _ { - } > 0$) a vector of $\mathbb { R } ^ { n - 1 }$ and $S _ { + }$ (resp. $S _ { - }$) the sign diagonal matrix, such that $Q _ { + } x _ { + } = S _ { + } x _ { + }$, resp. $Q _ { - } x _ { - } = S _ { - } x _ { - }$. We set

• $\eta _ { + } = - \frac { \left( x _ { + } \mid q \right) } { \alpha + 1 } , \quad \eta _ { - } = - \frac { \left( x _ { - } \mid q \right) } { \alpha - 1 }$
• $z _ { + } = \binom { x _ { + } } { \eta _ { + } } , \quad z _ { - } = \binom { x _ { - } } { \eta _ { - } }$
• $S ^ { + } = \left( \begin{array} { c c } S _ { + } & 0 \\ 0 & + 1 \end{array} \right) , \quad S ^ { - } = \left( \begin{array} { c c } S _ { - } & 0 \\ 0 & - 1 \end{array} \right)$

Show using question 1(a) that in the case where $S _ { + } \neq S _ { - }$ then one of the pairs $(z _ { + } , S ^ { + })$ or $(z _ { - } , S ^ { - })$ satisfies Broyden's theorem.

We now assume that $S _ { + } = S _ { - }$ and we assume that $\left( x _ { + } \mid q \right) = 0$. We denote by $z = \binom { x _ { + } } { 0 }$, $R ^ { + } = \left( \begin{array} { c c } S _ { + } & 0 \\ 0 & + 1 \end{array} \right) , R ^ { - } = \left( \begin{array} { c c } S _ { + } & 0 \\ 0 & - 1 \end{array} \right)$.
(a) Show that $O z = R^{+} z = R^{-} z$.
(b) We now write $$O = \left( \begin{array} { c c } \alpha ^ { \prime } & { } ^ { t } q ^ { \prime } \\ r ^ { \prime } & P ^ { \prime } \end{array} \right)$$ where $P ^ { \prime } \in M _ { n - 1 } ( \mathbb { R } )$. Construct then $z ^ { \prime } = \binom { \eta ^ { \prime } } { x ^ { \prime } } \in \mathbb { R } ^ { n }$ with $x ^ { \prime } \in \mathbb { R } ^ { n - 1 }$ strictly positive and $\eta ^ { \prime } \geq 0$ such that there exists a sign diagonal matrix $R ^ { \prime }$ satisfying $O z ^ { \prime } = R ^ { \prime } z ^ { \prime }$.
(c) In the case where $\eta ^ { \prime } = 0$, and using question 1(c), show that there exists a sign diagonal matrix $S$ such that $O \left( z + z ^ { \prime } \right) = S \left( z + z ^ { \prime } \right)$ and conclude.

For $A \in M _ { n , m } ( \mathbb { R } )$ and $b \in \mathbb { R } ^ { n }$ as in Farkas' lemma, we set $$B = \left( \begin{array} { c c c c } 0 & 0 & A & - b \\ 0 & 0 & - A & b \\ - { } ^ { t } A & { } ^ { t } A & 0 & 0 \\ { } ^ { t } b & - { } ^ { t } b & 0 & 0 \end{array} \right)$$ Let, by Tucker's theorem, $y = { } ^ { t } \left( z _ { 1 } , z _ { 2 } , x , t \right) \geq 0$ such that $B y \geq 0$ and $y + B y > 0$.
Show that if $t > 0$ then for $z = z _ { 1 } - z _ { 2 }$, we have $- { } ^ { t } A z \geq 0$ and $( b \mid z ) > 0$.

For $A \in M _ { n , m } ( \mathbb { R } )$ and $b \in \mathbb { R } ^ { n }$ as in Farkas' lemma, we set $$B = \left( \begin{array} { c c c c } 0 & 0 & A & - b \\ 0 & 0 & - A & b \\ - { } ^ { t } A & { } ^ { t } A & 0 & 0 \\ { } ^ { t } b & - { } ^ { t } b & 0 & 0 \end{array} \right)$$ Let, by Tucker's theorem, $y = { } ^ { t } \left( z _ { 1 } , z _ { 2 } , x , t \right) \geq 0$ such that $B y \geq 0$ and $y + B y > 0$.
If $t > 0$ show that $A x = t b$ and conclude.

Let $k$ and $n$ be two strictly positive integers. Show that there exists only a finite number of partitions of the set $\llbracket 1 , n \rrbracket$ into $k$ parts.

Throughout the problem, for every pair $( n , k )$ of strictly positive integers, we denote by $S ( n , k )$ the number of partitions of the set $\llbracket 1 , n \rrbracket$ into $k$ parts. We further set $S ( 0,0 ) = 1$ and, for all $( n , k ) \in \mathbb { N } ^ { * 2 } , S ( n , 0 ) = S ( 0 , k ) = 0$.
Express $S ( n , k )$ as a function of $n$ or of $k$ in the following cases:
I.B.1) $k > n$;
I.B.2) $k = 1$.

Throughout the problem, for every pair $( n , k )$ of strictly positive integers, we denote by $S ( n , k )$ the number of partitions of the set $\llbracket 1 , n \rrbracket$ into $k$ parts. We further set $S ( 0,0 ) = 1$ and, for all $( n , k ) \in \mathbb { N } ^ { * 2 } , S ( n , 0 ) = S ( 0 , k ) = 0$.
Show that for all strictly positive integers $k$ and $n$, we have $$S ( n , k ) = S ( n - 1 , k - 1 ) + k S ( n - 1 , k )$$ One may distinguish the partitions of $\llbracket 1 , n \rrbracket$ according to whether or not they contain the singleton $\{ n \}$.

We set for every integer $n \geqslant 0$, $$B _ { n } = \sum _ { k = 0 } ^ { n } S ( n , k )$$ where $S(n,k)$ denotes the number of partitions of $\llbracket 1, n \rrbracket$ into $k$ parts.
Show that for $n \geqslant 1$, $B _ { n }$ equals the total number of partitions of the set $\llbracket 1 , n \rrbracket$.

We set for every integer $n \geqslant 0$, $$B _ { n } = \sum _ { k = 0 } ^ { n } S ( n , k )$$ where $S(n,k)$ denotes the number of partitions of $\llbracket 1, n \rrbracket$ into $k$ parts.
Prove the formula $$\forall n \in \mathbb { N } , \quad B _ { n + 1 } = \sum _ { k = 0 } ^ { n } \binom { n } { k } B _ { k }$$

We set for every integer $n \geqslant 0$, $$B _ { n } = \sum _ { k = 0 } ^ { n } S ( n , k )$$ where $S(n,k)$ denotes the number of partitions of $\llbracket 1, n \rrbracket$ into $k$ parts.
Show that the sequence $\left( \frac { B _ { n } } { n ! } \right) _ { n \in \mathbb { N } }$ is bounded by 1.

We set for every integer $n \geqslant 0$, $$B _ { n } = \sum _ { k = 0 } ^ { n } S ( n , k )$$ where $S(n,k)$ denotes the number of partitions of $\llbracket 1, n \rrbracket$ into $k$ parts. The sequence $\left( \frac { B _ { n } } { n ! } \right) _ { n \in \mathbb { N } }$ is bounded by 1.
Deduce a lower bound for the radius of convergence $R$ of the power series $\sum _ { n \geqslant 0 } \frac { B _ { n } } { n ! } z ^ { n }$.

We set for every integer $n \geqslant 0$, $$B _ { n } = \sum _ { k = 0 } ^ { n } S ( n , k )$$ where $S(n,k)$ denotes the number of partitions of $\llbracket 1, n \rrbracket$ into $k$ parts. Let $R$ be the radius of convergence of the power series $\sum _ { n \geqslant 0 } \frac { B _ { n } } { n ! } z ^ { n }$, and for $x \in ] - R , R [$, set $f ( x ) = \sum _ { n = 0 } ^ { + \infty } \frac { B _ { n } } { n ! } x ^ { n }$.
Show that for all $x \in ] - R , R [ , f ^ { \prime } ( x ) = \mathrm { e } ^ { x } f ( x )$.

We set for every integer $n \geqslant 0$, $$B _ { n } = \sum _ { k = 0 } ^ { n } S ( n , k )$$ where $S(n,k)$ denotes the number of partitions of $\llbracket 1, n \rrbracket$ into $k$ parts. Let $R$ be the radius of convergence of the power series $\sum _ { n \geqslant 0 } \frac { B _ { n } } { n ! } z ^ { n }$, and for $x \in ] - R , R [$, set $f ( x ) = \sum _ { n = 0 } ^ { + \infty } \frac { B _ { n } } { n ! } x ^ { n }$. It has been shown that $f ^ { \prime } ( x ) = \mathrm { e } ^ { x } f ( x )$ for all $x \in ] - R , R [$.
Deduce an expression for the function $f$ on $] - R , R [$.

We define the sequence of polynomials $\left( H _ { k } \right) _ { k \in \mathbb { N } }$ in $\mathbb { R } [ X ]$ by $H _ { 0 } ( X ) = 1$ and, for all $k \in \mathbb { N } ^ { * }$, $$H _ { k } ( X ) = X ( X - 1 ) \cdots ( X - k + 1 )$$
Show that the family $( H _ { 0 } , \ldots , H _ { n } )$ is a basis of the space $\mathbb { R } _ { n } [ X ]$.

Let $A(T) \in \mathbb{R}[T]$ be the polynomial: $A(T) = T^{4} + 2T + 1$.
a) Let $U(T)$ and $V(T)$ be two polynomials with non-negative real coefficients such that $U(T)V(T) = A(T)$. Show that one of the polynomials $U(T)$ or $V(T)$ is constant.
One may distinguish cases according to the values of the degrees of $U(T)$ and $V(T)$.
b) Deduce that there exists a decomposable random variable $X$ such that $X^{2}$ is not decomposable.
One may consider the polynomial $\frac{1}{4}A(T)$.

Is the set $E^{c}$ a vector subspace of $\mathbb{R}^{\mathbb{N}}$?

Let $\left(u_{n}\right)_{n \in \mathbb{N}}$ be an element of $E^{c}$. Show that $\ell^{c}$ belongs to the segment $[0,1]$.

We denote $E_{n} = \mathcal{M}_{n,1}(\mathbb{R})$ equipped with the inner product $(X \mid Y) = X^{\top}Y$. A matrix $K \in \mathcal{M}_{n}(\mathbb{R})$ is called $F$-singular if there exists a non-zero $X \in F$ such that $\forall Z \in F, Z^{\top}KX = 0$. We assume $n \geqslant 2$. $A$ is an invertible matrix in $\mathcal{M}_{n}(\mathbb{R})$.
We assume that $A_{s} \in \mathcal{S}_{n}^{++}(\mathbb{R})$. Show that $A$ is $H$-regular for every hyperplane $H$ of $E_{n}$.

We consider the matrix $$A = A(\mu) = \begin{pmatrix} 2-\mu & -1 & \mu \\ -1 & 2-\mu & \mu-1 \\ 0 & -1 & 1 \end{pmatrix}$$
Show that $A(\mu)$ is invertible for every real $\mu$.

We consider the matrix $$A = A(\mu) = \begin{pmatrix} 2-\mu & -1 & \mu \\ -1 & 2-\mu & \mu-1 \\ 0 & -1 & 1 \end{pmatrix}$$
Calculate $A(\mu)_{s}$ and show that $A(\mu)_{s}$ is singular for $\mu = 1, 1-\sqrt{3}, 1+\sqrt{3}$.

We consider the matrix $$A = A(\mu) = \begin{pmatrix} 2-\mu & -1 & \mu \\ -1 & 2-\mu & \mu-1 \\ 0 & -1 & 1 \end{pmatrix}$$
A matrix $K \in \mathcal{M}_{n}(\mathbb{R})$ is called $F$-singular if there exists a non-zero $X \in F$ such that $\forall Z \in F, Z^{\top}KX = 0$.
Determine a hyperplane $H$ such that $A(1)$ is $H$-singular.

We denote $E_{n} = \mathcal{M}_{n,1}(\mathbb{R})$ equipped with the inner product $(X \mid Y) = X^{\top}Y$. A matrix $K \in \mathcal{M}_{n}(\mathbb{R})$ is called $F$-singular if there exists a non-zero $X \in F$ such that $\forall Z \in F, Z^{\top}KX = 0$. We assume $n \geqslant 3$. Let $F$ be a vector subspace of $E_{n}$ of dimension $n-2$. We consider $(N_{1}, N_{2})$ a basis of $F^{\perp}$ and we set $N = \begin{pmatrix} N_{1} & N_{2} \end{pmatrix} \in \mathcal{M}_{n,2}(\mathbb{R})$.
Show that $A$ is $F$-singular if and only if there exist a non-zero element $X$ of $F$ and two real numbers $\lambda_{1}$, $\lambda_{2}$ such that $AX = \lambda_{1}N_{1} + \lambda_{2}N_{2}$.

We denote $E_{n} = \mathcal{M}_{n,1}(\mathbb{R})$ equipped with the inner product $(X \mid Y) = X^{\top}Y$. A matrix $K \in \mathcal{M}_{n}(\mathbb{R})$ is called $F$-singular if there exists a non-zero $X \in F$ such that $\forall Z \in F, Z^{\top}KX = 0$. We assume $n \geqslant 3$. Let $F$ be a vector subspace of $E_{n}$ of dimension $n-2$. We consider $(N_{1}, N_{2})$ a basis of $F^{\perp}$ and we set $N = \begin{pmatrix} N_{1} & N_{2} \end{pmatrix} \in \mathcal{M}_{n,2}(\mathbb{R})$.
Deduce that $A$ is $F$-singular if and only if the matrix $$A_{N} = \begin{pmatrix} A & N_{1} & N_{2} \\ N_{1}^{\top} & 0 & 0 \\ N_{2}^{\top} & 0 & 0 \end{pmatrix} = \begin{pmatrix} A & N \\ N^{\top} & 0_{2} \end{pmatrix} \in \mathcal{M}_{n+2}(\mathbb{R})$$ is singular.

We denote $E_{n} = \mathcal{M}_{n,1}(\mathbb{R})$ equipped with the inner product $(X \mid Y) = X^{\top}Y$. We assume $n \geqslant 3$. Let $F$ be a vector subspace of $E_{n}$ of dimension $n-2$. We consider $(N_{1}, N_{2})$ a basis of $F^{\perp}$ and we set $N = \begin{pmatrix} N_{1} & N_{2} \end{pmatrix} \in \mathcal{M}_{n,2}(\mathbb{R})$. $A$ is an invertible matrix in $\mathcal{M}_{n}(\mathbb{R})$.
Show that there exists a matrix $B = \begin{pmatrix} B_{1} & B_{2} \\ B_{3} & B_{4} \end{pmatrix}$ with $B_{1} \in \mathcal{M}_{n}(\mathbb{R}), B_{2} \in \mathcal{M}_{n,2}(\mathbb{R}), B_{3} \in \mathcal{M}_{2,n}(\mathbb{R})$ and $B_{4} \in \mathcal{M}_{2}(\mathbb{R})$ such that $$A_{N}B = \begin{pmatrix} I_{n} & 0 \\ N^{\top}A^{-1} & -N^{\top}A^{-1}N \end{pmatrix}$$