Home > Algebra, Linear Algebra > Agregation 2014 – Mathematiques Generales – Parts 4-6

## Agregation 2014 – Mathematiques Generales – Parts 4-6

This is the second part of the Mathematiques Generales French Agregation written exam 2014. For the complete notation list and the first three parts look at this post.

Part 4 – Reduced form of permutations

For ${n \geq 2}$ we denote ${\Gamma}$ the set of pairs ${(i,j)}$ such that ${1\leq i. We call the set of inversions of a permutation ${\sigma \in S_n}$ the set

$\displaystyle I(\sigma) = \{(i,j) \in \Gamma : \sigma(i)>\sigma(j)\}$

and we denote ${N(\sigma)}$ the cardinal of ${I(\sigma)}$.

1. For which permutations ${\sigma \in S_n}$ is the number ${N(\sigma)}$ maximum?

For ${k \in [1..n-1]}$ we denote ${\tau_k \in S_k}$ the transposition which changes ${k}$ and ${k+1}$.

4.2 (a) Let ${(k,\sigma) \in [1..n-1]\times S_n}$. Prove that

$\displaystyle N(\tau_k \circ \sigma) = \begin{cases} N(\sigma)+1 & \text{ if }\sigma^{-1}(k) < \sigma^{-1}(k+1)\\ N(\sigma)-1 & \text{ if }\sigma^{-1}(k) > \sigma^{-1}(k+1), \end{cases}$

and that ${I(\tau_k \circ \sigma)}$ is obtained from ${I(\sigma)}$ by adding or removing an element of ${\Gamma}$.

(b) Find explicitly ${\sigma^{-1} \circ \tau_k \circ \sigma}$ in function of the element of ${I(\tau_k \circ \sigma)}$ which makes it differ from ${I(\sigma)}$.

Let ${T= \{ \tau_1,...,\tau_{n-1} \}}$. We call word a finite sequence ${m=(t_1,...,t_l)}$ of elements of ${T}$. We say that ${l}$ is the length of ${m}$ and that the elements ${t_1,..,t_l}$ are the letters of ${m}$. The case of a void word ${(l=0)}$ is authorized.

A writing of a permutation ${\sigma \in S_n}$ is a word ${m=(t_1,...,t_l)}$ such that ${\sigma =(t_1,...,t_l)}$. We make the convention that the permutation which corresponds to the void word is the identity.

4.3 (a) Prove that the group ${S_n}$ is generated by ${T}$.

(b) Let ${\sigma \in S_n}$. Prove that ${\sigma}$ has a writing of length ${N(\sigma)}$ and that every writing of ${\sigma}$ is of length at least ${N(\sigma)}$.

A writing of a permutation ${\sigma \in S_n}$ is called reduced if its length is ${N(\sigma)}$.

4.4 Find a reduce writing of each of the elements of ${S_3}$.

4.5 Let ${\sigma \in S_n}$ and ${(t_1,...,t_l)}$ be a non-reduced writing of ${\sigma}$. Prove that ther exist two integers ${1\leq p such that ${(t_1,...,t_{p-1},t_{p+1},...,t_{q-1},t_{q+1},...,t_l)}$ is a writing of ${\sigma}$.

The result of question 4.5 can be interpreted like this: if a word ${m}$ is a non-reduced writing of a permutation ${\sigma \in S_n}$, then we can obtain a shorter writing for ${\sigma}$ by ommiting from ${m}$ two letters chosen conveniently. Repeating this operation as long as it takes, we arrive at extracting from ${m}$ a reduced writing of ${\sigma}$.

4.6 Consider ${m,m'}$ two reduced writings of a permutation ${\sigma \in S_n}$ different from identity. Let ${\tau_i}$ be the first letter of ${m}$ and ${\tau_j}$ the first letter of ${m'}$.

(a) Suppose that ${i \neq j}$. Prove that ${\sigma}$ has a reduced writing ${m^{''}}$ starting with ${(\tau_j,\tau_i)}$.

(b) Suppose that ${|i-j|=1}$. Prove that ${\sigma}$ has a reduced writing ${m^{''}}$ starting with ${(\tau_i,\tau_j,\tau_i)}$.

Given two words ${m,m'}$ of the same length ${l}$ we write ${m \approx m'}$ if we are in one of the following situations:
– There exists a word ${(t_1,...,t_{l-2})}$ and elements ${p \in [0..l-2]}$ and ${(i,j) \in [1,n-1]^2}$ such that ${|i-j| \geq 2}$,

$\displaystyle m=(t_1,...,t_p,\tau_i,\tau_j,t_{p+1},...,t_{l-2}) \text{ and } m'=(t_1,...,t_p,\tau_j,\tau_i,t_{p+1},...,t_{l-2}).$

– There exists a word ${(t_1,...,t_{l-3})}$ and elements ${p \in [0..l-3]}$ and ${(i,j) \in [1,n-1]^2}$ such that ${|i-j| =1}$,

$\displaystyle m=(t_1,...,t_p,\tau_i,\tau_j,\tau_i,t_{p+1},...,t_{l-3}) \text{ and } m'=(t_1,...,t_p,\tau_j,\tau_i,\tau_j,t_{p+1},...,t_{l-3}).$

We write ${m \sim m'}$ if there is a finite sequence ${(m_0,...,m_k)}$ of words such that

$\displaystyle m=m_0 \approx m_1 \approx ... \approx m_{k-1} \approx m_k =m'.$

(The case ${k=0}$ which corresponds at ${m=m'}$ is authorized.)

4.7 (a) Let ${m=(t_1,...,t_l)}$ and ${m'=(t_1',...,t_l')}$ be two words of the same length. Prove that if ${m\sim m'}$ then ${t_1 \circ ... \circ t_l = t_1'\circ ... \circ t_l'}$.

(b) Let ${m}$ and ${m'}$ be two reduced writings of the same permutation. Prove that ${m\sim m'}$.

Part 5 – Bruhat Decomposition

In this part ${n \geq 2}$ and ${\Bbb{K}}$ is a field. Let ${E}$ be the vector space ${\Bbb{K}^n}$ with its standard base ${(e_1,...,e_n)}$. We identify ${GL(E)}$ and ${GL_n(\Bbb{K})}$.

We call standard flag the flag ${(F_0,F_1,...,F_n)}$ where ${F_0=\{0\}}$ and for ${k \geq 1}$ ${F_k}$ is the vector space spanned by ${\{e_1,...,e_k\}}$.

We denote ${B}$ the subgroup of ${GL_n(\Bbb{K})}$ formed of the matrices which are invertible and upper triangular.

To every permutation ${\sigma \in S_n}$ there corresponds a permutation matrix ${P_\sigma}$ defined in Part 3. It is a matrix with coefficients in ${\{0,1\}}$ that belongs to ${GL_n(\Bbb{K})}$. We denote ${C(\sigma)}$ the set of matrices of the form ${b'P_\sigma b''}$ witn ${b',b'' \in B}$. This is a subset of ${GK_n(\Bbb{K})}$.

5.1 For this question we take ${\Bbb{K}=\Bbb{R}}$ or ${\Bbb{C}}$. Denote ${\sigma_0 \in S_n}$ the permutation defined by ${\sigma_0(i)=n+1-i}$, for ${i=[1..n]}$. Prove that ${C(\sigma_0)}$ is dense in ${GL_n(\Bbb{K})}$.
(Indication: use Theorem D)

For ${k \in [1..n-1]}$ and ${\alpha \in \Bbb{K}}$ we denote ${y_k(a)}$ the ${n \times n}$ matrix with coefficients in ${\Bbb{K}}$ with ${1}$ on the diagonal and ${a}$ in position ${(k+1,k)}$ and zero everywhere else.

5.2 Prove that ${y_k(a) \in C(\tau_k)}$ for every ${(k,a) \in [1..n-1]\times \Bbb{K}^*}$.

We use the notations from Part 3.

5.3 Let ${\Bbb{F}}$ be the standard flag.

(a) Prove that ${B}$ is the stabilizer of ${\Bbb{F}}$.

(b) Prove that for every ${\sigma \in S_n}$ the pair of flags ${(\Bbb{F},P_\sigma \cdot \Bbb{F})}$ is in position ${\sigma}$.

(c) Prove that for every ${\sigma \in S_n}$ we have ${C(\sigma) = \{g \in GL_n(\Bbb{K}) : (\Bbb{F},g \cdot \Bbb{F}) \in \mathcal{O}_\sigma\}}$.

(d) Prove that ${GL_n(\Bbb{K})}$ is the disjoint union of ${C(\sigma)}$, i.e. ${GL_n(\Bbb{K})= \displaystyle\bigcup_{\sigma \in S_n} C(\sigma)}$ and that the ${C(\sigma)}$ are pairwise disjoint.

Given two subsets ${C,D}$ of ${GL_n(\Bbb{K})}$ we denote ${CD = \{ gh : (g,h) \in C \times D\}}$. We use the notations of Part 4.

5.4 Let ${(\sigma,k) \in S_n \times [1..n-1]}$ such that ${N(\tau_k \circ \sigma)>N(\sigma)}$.

(a) Prove that for every ${g \in C(\sigma)}$ the product ${P_{\tau_k} g}$ belongs to ${C(\tau_k \circ \sigma)}$.
(Indication: use 3.7 (b))

(b) Deduce that ${C(\tau_k)C(\sigma)=C(\tau_k \circ sigma)}$.

From question 5.4 we deduce that for every permutation ${\sigma \in S_n}$ and every reduced writing ${(t_1,...,t_l)}$ of ${\sigma}$ we have

$\displaystyle C(\sigma) = C(t_1)C(t_2)...C(t_l).$

The end of this part has the objective of finding the closures of ${C(\sigma)}$. To give a meaning to this probleme we place ourselves in the cases ${\Bbb{K}=\Bbb{R}}$ or ${\Bbb{C}}$.

Given two permutations ${\rho}$ and ${\sigma}$ we write ${\rho \leq \sigma}$ if for every ${(i,j) \in [0,n]^2}$ we have ${d_{i,j}(\rho) \geq d_{i,j}(\sigma)}$.

5.5 (a) Prove that ${\leq}$ is an order relation on ${S_n}$.

(b) Prove that the identity permutation is the smallest element of ${S_n}$ for the order ${\leq}$.

(c) Does the set ${S_n}$ endowed with the order relation ${\leq}$ has a largest element?

5.6 Let ${(\rho,\sigma) \in S_n^2}$ such that ${\rho \leq \sigma}$ and let ${k \in [1..n-1]}$. Prove that:

(a) If ${N(\tau_k \circ \rho) < N(\rho)}$ then ${\tau_k \circ \rho \leq \tau_k \circ \sigma}$.

(b) If ${N(\tau_k \circ \rho)>N(\rho)}$ then ${\rho \leq \tau_k \circ \sigma}$.

5.7 Let ${\hat E}$ be a ${\Bbb{K}}$ vector space of finite dimension and ${F,G}$ be two linear subspaces of ${\hat E}$ and ${d}$ a positive integer. Prove that

$\displaystyle \{ g \in GL(\hat E) : \dim(F \cap g(G)) \geq d\}$

is a closed subset of ${GL(\hat E)}$.

5.8 Let ${(\sigma,\rho) \in S_n^2}$. Prove that the following four statements are equivalent.
(i) ${\rho \leq \sigma}$.
(ii) For every reduced writing ${(t_1,...,t_l)}$ of ${\sigma}$ there exists a strictly increasing sequence of indices ${1 \leq i_1 <... such that ${(t_{i_1},...,t_{i_k})}$ is a reduced writing of ${\rho}$.
(iii) There exists a reduced writing ${(t_1,...,t_\sigma)}$ of ${\sigma}$ and a strictly increasing sequence of indices ${1 \leq i_1 <... such that ${(t_{i_1},...,t_{i_k})}$ is a reduced writing of ${\rho}$.
(iv) The set ${C(\rho)}$ is included in the closure of ${C(\sigma)}$ in ${GL_n(\Bbb{K})}$.

5.9 Prove that for every ${\sigma \in S_n}$ the closure of ${C(\sigma)}$ in ${GL_n(\Bbb{K})}$ is given by

$\displaystyle \overline{C(\sigma)} = \bigcup_{\substack{\rho \in S_n \\ \rho \leq \sigma}} C(\rho).$

Part 6 – Unitriangular totally positive matrices

As noted in the end of the second part, we study here the set of inferior unitriangular ${TP}$ matrices. In the following all matrices are considered of size ${n \times n}$, where ${n \geq 2}$.

Like in Part 5 we denote for ${k \in [1..n-1]}$ and ${a \in \Bbb{R}}$ ${y_k(a)}$ the matrix with ${1}$ on the diagonal and ${a}$ in position ${(k+1,k)}$ with zeros elswhere. We can easily verify that ${y_k(a)}$ is TP if and only if ${a \geq 0}$. Therefore the product of such matrices is TP.

Using the notations of Part 4 each word ${m=(\tau_{k_1},...,\tau_{k_l})}$ defines an application ${Y(M) : (\Bbb{R}_+^*)^l \rightarrow \mathcal{M}_n(\Bbb{R})}$ defined by

$\displaystyle Y(m)(a_1,...,a_l)= y_{k_1}(a_1)...y_{k_l}(a_l).$

If ${m}$ is the void word, then the domain of definition of ${Y(m)}$ contains only one element and we define ${Y(m)}$ to be the identity matrix on that element.

6.1 In this question we study the case ${n=3}$.

(a) On the example of the word ${m=(\tau_2,\tau_1)}$ prove that the image of ${Y(m)}$ is a sub-manifold of ${\mathcal{M}_3(\Bbb{R})}$.

(b) Let ${m_1,...,m_6}$ be the six words found in question 4.4. Verify that the images of the applications ${Y(m_1),Y(m_2),...,Y(m_6)}$ are pairwise disjoint and that their union is the set of inferior unitriangular TP matrices.

The phenomenons observed in question 6.1 happen for every ${n \geq 2}$. In the following we will prove some partial results related to this.

6.2 Let ${(i,j) \in [1..n-1]^2}$ and ${a,b,c \in \Bbb{R}_+^*}$.

(a) Suppose that ${|i-j| \geq 2}$. Verify that ${y_i(a)y_j(b)=y_j(b)y_i(a)}$.

(b) Suppose that ${|i-j|=1}$. Prove that there existe a unique element ${(a',b',c') \in (\Bbb{R}_+^*)^3}$ such that

$\displaystyle y_i(a)y_j(b)y_i(c) = y_j(a')y_i(b')y_j(c').$

Is the application ${(a,b,c) \rightarrow (a',b',c')}$ from ${(\Bbb{R}_+^*)^3}$ to itself bijective?

The question 6.2 implies that ${Y(m)}$ and ${Y(m')}$ have the same image if ${m \approx m'}$, with the notation introduced in part 4. The question 4.7(b) shows that if we have ${\sigma \in S_n}$ then the image of ${Y(m)}$ is constant as ${m}$ runs through the set of reduced writings of ${\sigma}$. We denote that image ${W(\sigma)}$. The question 5.2 and the identity from 5.4(b) show that ${W(\sigma)\subset C(\sigma)}$. Therefore by question 5.3 the sets ${W(\sigma)}$ are pairwise disjoint.

6.3 (a) Let ${\sigma \in S_n}$, ${k \in [1..n-1]}$, ${a \in \Bbb{R}_+^*}$ and ${g \in W(\sigma)}$. Prove that ${y_k(a)g}$ belongs to ${W(\tau_k \circ \sigma)}$ if ${N(\tau_k \circ \sigma)>N(\sigma)}$ or to ${W(\sigma)}$ if the opposite holds.

(b) Let ${\sigma \in S_n}$, ${l=N(\sigma)}$ and ${m}$ a reduced writing of ${\sigma}$. Prove that the application ${Y(m) : (\Bbb{R}_+^*)^l \rightarrow W(\sigma)}$ is bijective.

6.4 (a) Prove that for every ${\sigma \in S_n}$ the closure of ${W(\sigma)}$ in ${GL_n(\Bbb{R})}$ is

$\displaystyle \overline{W(\sigma)} =\bigcup_{\substack{ \rho \in S_n \\ \rho \leq \sigma}} W(\rho).$

(b) Prove that ${\displaystyle \bigcup_{\sigma \in S_n} W(\sigma)}$ stable under multiplication and is closed in ${GL_n(\Bbb{R})}$.

We can prove that ${\displaystyle \bigcup_{\sigma \in S_n} W(\sigma)}$ is the set of inferior unitriangular TP matrices and that if ${m}$ is a reduced writing of a permutation, then the application ${Y(M) : (\Bbb{R}_+^*)^l \rightarrow \mathcal{M}_n(\Bbb{R})}$ is an extension which implies that ${W(\sigma)}$ are sub-manifolds of ${\mathcal{M}_n(\Bbb{R})}$.