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<j \leq n}. 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<q \leq l} 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 <...<i_k \leq l} 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 <...<i_k \leq l} 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})}.

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: