uniolympiads English

IMC 2009, Ημέρα 2, Θέμα 5

Let M\mathbb{M} be the vector space of m×pm \times p real matrices. For a vector subspace S⊆MS \subseteq \mathbb{M}, denote by δ(S)\delta(S) the dimension of the vector space generated by all columns of all matrices in SS.

Say that a vector subspace T⊆MT \subseteq \mathbb{M} is a covering matrix space if

⋃A∈T, A≠0ker⁡A=Rp.\bigcup_{A \in T,\ A \ne 0} \ker A = \mathbb{R}^p.

Such a TT is minimal if it does not contain a proper vector subspace S⊂TS \subset T which is also a covering matrix space.

(a) (8 points) Let TT be a minimal covering matrix space and let n=dim⁡Tn = \dim T. Prove that

δ(T)≤(n2).\delta(T) \le \binom{n}{2}.

(b) (2 points) Prove that for every positive integer nn we can find mm and pp, and a minimal covering matrix space TT as above such that dim⁡T=n\dim T = n and δ(T)=(n2)\delta(T) = \binom{n}{2}.

Πρωτότυπο από το επίσημο PDFLet M be the vector space of m × p real matrices. For a vector subspace S ⊆ M, denote by δ(S) the dimension of the vector space generated by all columns of all matrices in S. Say that a vector subspace T ⊆ M is a covering matrix space if [ ker A = R p . A∈T, A6 =0 Such a T is minimal if it does not contain a proper vector subspace S ⊂ T which is also a covering matrix space. (a) (8 points) Let T be a minimal covering matrix space and let n = dim T . Prove that n δ(T ) ≤ . 2 (b) (2 points) Prove that for every positive integer n we can find m and p, and a minimal covering matrix space n T as above such that dim T = n and δ(T ) = . 2

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

Solution 1. (a) We will prove the claim by constructing a suitable decomposition T=Z0⊕Z1⊕⋯T = Z_0 \oplus Z_1 \oplus \cdots and a corresponding decomposition of the space spanned by all columns of TT as W0⊕W1⊕⋯W_0 \oplus W_1 \oplus \cdots, such that dim⁡W0⩽n−1\dim W_0 \leqslant n-1, dim⁡W1⩽n−2\dim W_1 \leqslant n-2, etc., from which the bound follows.

We first claim that, in every covering matrix space SS, we can find an A∈SA \in S with rk⁡A⩽dim⁡S−1\operatorname{rk}A \leqslant \dim S - 1. Indeed, let S0⊆SS_0 \subseteq S be some minimal covering matrix space. Let s=dim⁡S0s = \dim S_0 and fix some subspace S′⊂S0S' \subset S_0 of dimension s−1s-1. S′S' is not covering by minimality of S0S_0, so that we can find an u∈Rpu \in \mathbb{R}^p with u∉∪B∈S′, B≠0Ker⁡Bu \notin \cup_{B\in S',\,B\ne 0}\operatorname{Ker}B. Let V=S′(u)V = S'(u); by the rank-nullity theorem, dim⁡V=s−1\dim V = s-1. On the other hand, as S0S_0 is covering, we have that Au=0Au = 0 for some A∈S0∖S′A \in S_0 \setminus S'. We claim that Im⁡A⊂V\operatorname{Im}A \subset V (and therefore rk⁡(A)⩽s−1\operatorname{rk}(A) \leqslant s-1).

For suppose that Av∉VAv \notin V for some v∈Rpv \in \mathbb{R}^p. For every α∈R\alpha \in \mathbb{R}, consider the map fα:S0→Rmf_\alpha : S_0 \to \mathbb{R}^m defined by fα:(τ+βA)↦τ(u+αv)+βAvf_\alpha : (\tau + \beta A) \mapsto \tau(u + \alpha v) + \beta Av, τ∈S′\tau \in S', β∈R\beta \in \mathbb{R}. Note that f0f_0 is of rank s=dim⁡S0s = \dim S_0 by our assumption, so that some s×ss \times s minor of the matrix of f0f_0 is non-zero. The corresponding minor of fαf_\alpha is thus a nonzero polynomial of α\alpha, so that it follows that rk⁡fα=s\operatorname{rk}f_\alpha = s for all but finitely many α\alpha. For such an α≠0\alpha \ne 0, we have that Ker⁡fα={0}\operatorname{Ker}f_\alpha = \{0\} and thus

0≠τ(u+αv)+βAv=(τ+α−1βA)(u+αv)0 \ne \tau(u + \alpha v) + \beta Av = (\tau + \alpha^{-1}\beta A)(u + \alpha v)
for all τ∈S′\tau \in S', β∈R\beta \in \mathbb{R} not both zero, so that B(u+αv)≠0B(u + \alpha v) \ne 0 for all nonzero B∈S0B \in S_0, a contradiction.

Let now TT be a minimal covering matrix space, and write dim⁡T=n\dim T = n. We have shown that we can find an A∈TA \in T such that W0=Im⁡AW_0 = \operatorname{Im}A satisfies w0=dim⁡W0⩽n−1w_0 = \dim W_0 \leqslant n-1. Denote Z0={B∈T:Im⁡B⊂W0}Z_0 = \{B \in T : \operatorname{Im}B \subset W_0\}; we know that t0=dim⁡Z0⩾1t_0 = \dim Z_0 \geqslant 1. If T=Z0T = Z_0, then δ(T)⩽n−1\delta(T) \leqslant n-1 and we are done. Else, write T=Z0⊕T1T = Z_0 \oplus T_1, also write Rm=W0⊕V1\mathbb{R}^m = W_0 \oplus V_1 and let π1:Rm→Rm\pi_1 : \mathbb{R}^m \to \mathbb{R}^m be the projection onto the V1V_1-component. We claim that

T1♯={π1τ1:τ1∈T1}T_1^\sharp = \{\pi_1\tau_1 : \tau_1 \in T_1\}
is also a covering matrix space. Note here that π1♯:T1→T1♯\pi_1^\sharp : T_1 \to T_1^\sharp, τ1↦(π1τ1)\tau_1 \mapsto (\pi_1\tau_1) is an isomorphism. In particular we note that δ(T)=w0+δ(T1♯)\delta(T) = w_0 + \delta(T_1^\sharp).

Suppose that T1♯T_1^\sharp is not a covering matrix space, so we can find a v1∈Rpv_1 \in \mathbb{R}^p with v1∉∪τ1∈T1,τ1≠0Ker⁡(π1τ1)v_1 \notin \cup_{\tau_1\in T_1,\tau_1\ne 0}\operatorname{Ker}(\pi_1\tau_1). On the other hand, by minimality of TT we can find a u1∈Rpu_1 \in \mathbb{R}^p with u1∉∪τ0∈Z0, τ0≠0Ker⁡τ0u_1 \notin \cup_{\tau_0\in Z_0,\,\tau_0\ne 0}\operatorname{Ker}\tau_0. The maps gα:Z0→Vg_\alpha : Z_0 \to V, τ0↦τ0(u1+αv1)\tau_0 \mapsto \tau_0(u_1 + \alpha v_1) and hβ:T1→V1h_\beta : T_1 \to V_1, τ1↦π1(τ1(v1+βu1))\tau_1 \mapsto \pi_1(\tau_1(v_1 + \beta u_1)) have rk⁡g0=t0\operatorname{rk}g_0 = t_0 and rk⁡h0=n−t0\operatorname{rk}h_0 = n - t_0 and thus both rk⁡gα=t0\operatorname{rk}g_\alpha = t_0 and rk⁡hα−1=n−t0\operatorname{rk}h_{\alpha^{-1}} = n - t_0 for all but finitely many α≠0\alpha \ne 0 by the same argument as above. Pick such an α\alpha and suppose that

(τ0+τ1)(u1+αv1)=0(\tau_0 + \tau_1)(u_1 + \alpha v_1) = 0
for some τ0∈Z0\tau_0 \in Z_0, τ1∈T1\tau_1 \in T_1. Applying π1\pi_1 to both sides we see that we can only have τ1=0\tau_1 = 0, and then τ0=0\tau_0 = 0 as well, a contradiction given that TT is a covering matrix space.

In fact, the exact same proof shows that, in general, if TT is a minimal covering matrix space, Rm=V0⊕V1\mathbb{R}^m = V_0 \oplus V_1, T0={τ∈T:Im⁡τ⊂V0}T_0 = \{\tau \in T : \operatorname{Im}\tau \subset V_0\}, T=T0⊕T1T = T_0 \oplus T_1, π1:Rm→Rm\pi_1 : \mathbb{R}^m \to \mathbb{R}^m is the projection onto the V1V_1-component, and T1♯={π1τ1:τ1∈T1}T_1^\sharp = \{\pi_1\tau_1 : \tau_1 \in T_1\}, then T1♯T_1^\sharp is a covering matrix space.

We can now repeat the process. We choose a π1A1∈T1♯\pi_1A_1 \in T_1^\sharp such that W1=(π1A1)(Rp)W_1 = (\pi_1A_1)(\mathbb{R}^p) has w1=dim⁡W1⩽n−t0−1⩽n−2w_1 = \dim W_1 \leqslant n - t_0 - 1 \leqslant n-2. We write Z1={τ1∈T1:Im⁡(π1τ1)⊂W1}Z_1 = \{\tau_1 \in T_1 : \operatorname{Im}(\pi_1\tau_1) \subset W_1\}, T1=Z1⊕T2T_1 = Z_1 \oplus T_2 (and so T=(Z0⊕Z1)⊕T2T = (Z_0 \oplus Z_1) \oplus T_2), t1=dim⁡Z1⩾1t_1 = \dim Z_1 \geqslant 1, V1=W1⊕V2V_1 = W_1 \oplus V_2 (and so Rm=(W0⊕W1)⊕V2\mathbb{R}^m = (W_0 \oplus W_1) \oplus V_2), π2:Rm→Rm\pi_2 : \mathbb{R}^m \to \mathbb{R}^m is the projection onto the V2V_2-component, and T2♯={π2τ2:τ2∈T2}T_2^\sharp = \{\pi_2\tau_2 : \tau_2 \in T_2\}, so that T2♯T_2^\sharp is also a covering matrix space, etc.

We conclude that

δ(T)=w0+δ(T1)=w0+w1+δ(T2)=⋯⩽(n−1)+(n−2)+⋯⩽(n2).\begin{aligned} \delta(T) &= w_0 + \delta(T_1) = w_0 + w_1 + \delta(T_2) = \cdots \\ &\leqslant (n-1) + (n-2) + \cdots \leqslant \binom{n}{2}. \end{aligned}

(b) We consider (n2)×n\binom{n}{2} \times n matrices whose rows are indexed by (n2)\binom{n}{2} pairs (i,j)(i,j) of integers 1⩽i<j⩽n1 \leqslant i < j \leqslant n. For every u=(u1,u2,…,un)∈Rnu = (u_1, u_2, \ldots, u_n) \in \mathbb{R}^n, consider the matrix A(u)A(u) whose entries A(u)(i,j),kA(u)_{(i,j),k} with 1⩽i<j⩽n1 \leqslant i < j \leqslant n and 1⩽k⩽n1 \leqslant k \leqslant n are given by

(A(u))(i,j),k={ui,k=j,−uj,k=i,0,otherwise.(A(u))_{(i,j),k} = \begin{cases} u_i, & k = j, \\ -u_j, & k = i, \\ 0, & \text{otherwise.} \end{cases}
It is immediate that Ker⁡A(u)=R⋅u\operatorname{Ker}A(u) = \mathbb{R}\cdot u for every u≠0u \ne 0, so that S={A(u):u∈Rn}S = \{A(u) : u \in \mathbb{R}^n\} is a covering matrix space, and in fact a minimal one.

On the other hand, for any 1⩽i<j⩽n1 \leqslant i < j \leqslant n, we have that A(ei)(i,j),jA(e_i)_{(i,j),j} is the (i,j)th(i,j)^{\text{th}} vector in the standard basis of R(n2)\mathbb{R}^{\binom{n}{2}}, where eie_i denotes the ithi^{\text{th}} vector in the standard basis of Rn\mathbb{R}^n. This means that δ(S)=(n2)\delta(S) = \binom{n}{2}, as required.

Solution 2. (for part a)

Let us denote X=RpX = \mathbb{R}^p, Y=RmY = \mathbb{R}^m. For each x∈Xx \in X, denote by μx:T→Y\mu_x : T \to Y the evaluation map τ↦τ(x)\tau \mapsto \tau(x). As TT is a covering matrix space, ker⁡μx>0\ker\mu_x > 0 for every x∈Xx \in X. Let U={x∈X:dim⁡ker⁡μx=1}U = \{x \in X : \dim\ker\mu_x = 1\}.

Let T1T_1 be the span of the family of subspaces {ker⁡μx:x∈U}\{\ker\mu_x : x \in U\}. We claim that T1=TT_1 = T. For suppose the contrary, and let T′⊂TT' \subset T be a subspace of TT of dimension n−1n-1 such that T1⊆T′T_1 \subseteq T'. This implies that T′T' is a covering matrix space. Indeed, for x∈Ux \in U, (ker⁡μx)∩T′=ker⁡μx≠0(\ker\mu_x) \cap T' = \ker\mu_x \ne 0, while for x∉Ux \notin U we have dim⁡μx≥2\dim\mu_x \ge 2, so that (ker⁡μx)∩T′≠0(\ker\mu_x) \cap T' \ne 0 by computing dimensions. However, this is a contradiction as TT is minimal.

Now we may choose x1,x2,…,xn∈Ux_1, x_2, \ldots, x_n \in U and τ1,τ2,…,τn∈T\tau_1, \tau_2, \ldots, \tau_n \in T in such a way that ker⁡μxi=Rτi\ker\mu_{x_i} = \mathbb{R}\tau_i and τi\tau_i form a basis of TT. Let us complete x1,…,xnx_1, \ldots, x_n to a sequence x1,…,xdx_1, \ldots, x_d which spans XX. Put yij=τi(xj)y_{ij} = \tau_i(x_j). It is clear that yijy_{ij} span the vector space generated by the columns of all matrices in TT. We claim that the subset {yij:i>j}\{y_{ij} : i > j\} is enough to span this space, which clearly implies that δ(T)⩽(n2)\delta(T) \leqslant \binom{n}{2}.

We have yii=0y_{ii} = 0. So it is enough to show that every yijy_{ij} with i<ji < j can be expressed as a linear combination of ykiy_{ki}, k=1,…,nk = 1, \ldots, n. This follows from the following lemma:

Lemma. For every x0∈Ux_0 \in U, 0≠τ0∈ker⁡μx00 \ne \tau_0 \in \ker\mu_{x_0} and x∈Xx \in X, there exists a τ∈T\tau \in T such that τ0(x)=τ(x0)\tau_0(x) = \tau(x_0).

Proof. The operator μx0\mu_{x_0} has rank n−1n-1, which implies that for small ε\varepsilon the operator μx0+εx\mu_{x_0+\varepsilon x} also has rank n−1n-1. Therefore one can produce a rational function τ(ε)\tau(\varepsilon) with values in TT such that mx0+εx(τ(ε))=0m_{x_0+\varepsilon x}(\tau(\varepsilon)) = 0. Taking the derivative at ε=0\varepsilon = 0 gives μx0(τ0)+μx(τ′(0))=0\mu_{x_0}(\tau_0) + \mu_x(\tau'(0)) = 0. Therefore τ=−τ′(0)\tau = -\tau'(0) satisfies the desired property.

Remark. Lemma in solution 2 is the same as the claim Im⁡A⊂V\operatorname{Im}A \subset V at the beginning of solution 1, but the proof given here is different. It can be shown that all minimal covering spaces TT with dim⁡T=(n2)\dim T = \binom{n}{2} are essentially the ones described in our example.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 3–4. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;