Let 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
A∈T,A=0⋃kerA=Rp.
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=dimT. Prove that
δ(T)≤(2n).
(b) (2 points) Prove that for every positive integer n we can find m and p, and a minimal covering matrix space T as above such that dimT=n and δ(T)=(2n).
Πρωτότυπο από το επίσημο PDF
Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.
Χρόνος σε αυτό το θέμα
Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.
Επίσημη λύση
Solution 1. (a) We will prove the claim by constructing a suitable decomposition T=Z0⊕Z1⊕⋯ and a corresponding decomposition of the space spanned by all columns of T as W0⊕W1⊕⋯, such that dimW0⩽n−1, dimW1⩽n−2, etc., from which the bound follows.
We first claim that, in every covering matrix space S, we can find an A∈S with rkA⩽dimS−1. Indeed, let S0⊆S be some minimal covering matrix space. Let s=dimS0 and fix some subspace S′⊂S0 of dimension s−1. S′ is not covering by minimality of S0, so that we can find an u∈Rp with u∈/∪B∈S′,B=0KerB. Let V=S′(u); by the rank-nullity theorem, dimV=s−1. On the other hand, as S0 is covering, we have that Au=0 for some A∈S0∖S′. We claim that ImA⊂V (and therefore rk(A)⩽s−1).
For suppose that Av∈/V for some v∈Rp. For every α∈R, consider the map fα:S0→Rm defined by fα:(τ+βA)↦τ(u+αv)+βAv, τ∈S′, β∈R. Note that f0 is of rank s=dimS0 by our assumption, so that some s×s minor of the matrix of f0 is non-zero. The corresponding minor of fα is thus a nonzero polynomial of α, so that it follows that rkfα=s for all but finitely many α. For such an α=0, we have that Kerfα={0} and thus
0=τ(u+αv)+βAv=(τ+α−1βA)(u+αv)
for all τ∈S′, β∈R not both zero, so that B(u+αv)=0 for all nonzero B∈S0, a contradiction.
Let now T be a minimal covering matrix space, and write dimT=n. We have shown that we can find an A∈T such that W0=ImA satisfies w0=dimW0⩽n−1. Denote Z0={B∈T:ImB⊂W0}; we know that t0=dimZ0⩾1. If T=Z0, then δ(T)⩽n−1 and we are done. Else, write T=Z0⊕T1, also write Rm=W0⊕V1 and let π1:Rm→Rm be the projection onto the V1-component. We claim that
T1♯={π1τ1:τ1∈T1}
is also a covering matrix space. Note here that π1♯:T1→T1♯, τ1↦(π1τ1) is an isomorphism. In particular we note that δ(T)=w0+δ(T1♯).
Suppose that T1♯ is not a covering matrix space, so we can find a v1∈Rp with v1∈/∪τ1∈T1,τ1=0Ker(π1τ1). On the other hand, by minimality of T we can find a u1∈Rp with u1∈/∪τ0∈Z0,τ0=0Kerτ0. The maps gα:Z0→V, τ0↦τ0(u1+αv1) and hβ:T1→V1, τ1↦π1(τ1(v1+βu1)) have rkg0=t0 and rkh0=n−t0 and thus both rkgα=t0 and rkhα−1=n−t0 for all but finitely many α=0 by the same argument as above. Pick such an α and suppose that
(τ0+τ1)(u1+αv1)=0
for some τ0∈Z0, τ1∈T1. Applying π1 to both sides we see that we can only have τ1=0, and then τ0=0 as well, a contradiction given that T is a covering matrix space.
In fact, the exact same proof shows that, in general, if T is a minimal covering matrix space, Rm=V0⊕V1, T0={τ∈T:Imτ⊂V0}, T=T0⊕T1, π1:Rm→Rm is the projection onto the V1-component, and T1♯={π1τ1:τ1∈T1}, then T1♯ is a covering matrix space.
We can now repeat the process. We choose a π1A1∈T1♯ such that W1=(π1A1)(Rp) has w1=dimW1⩽n−t0−1⩽n−2. We write Z1={τ1∈T1:Im(π1τ1)⊂W1}, T1=Z1⊕T2 (and so T=(Z0⊕Z1)⊕T2), t1=dimZ1⩾1, V1=W1⊕V2 (and so Rm=(W0⊕W1)⊕V2), π2:Rm→Rm is the projection onto the V2-component, and T2♯={π2τ2:τ2∈T2}, so that T2♯ is also a covering matrix space, etc.
(b) We consider (2n)×n matrices whose rows are indexed by (2n) pairs (i,j) of integers 1⩽i<j⩽n. For every u=(u1,u2,…,un)∈Rn, consider the matrix A(u) whose entries A(u)(i,j),k with 1⩽i<j⩽n and 1⩽k⩽n are given by
It is immediate that KerA(u)=R⋅u for every u=0, so that S={A(u):u∈Rn} is a covering matrix space, and in fact a minimal one.
On the other hand, for any 1⩽i<j⩽n, we have that A(ei)(i,j),j is the (i,j)th vector in the standard basis of R(2n), where ei denotes the ith vector in the standard basis of Rn. This means that δ(S)=(2n), as required.
Solution 2. (for part a)
Let us denote X=Rp, Y=Rm. For each x∈X, denote by μx:T→Y the evaluation map τ↦τ(x). As T is a covering matrix space, kerμx>0 for every x∈X. Let U={x∈X:dimkerμx=1}.
Let T1 be the span of the family of subspaces {kerμx:x∈U}. We claim that T1=T. For suppose the contrary, and let T′⊂T be a subspace of T of dimension n−1 such that T1⊆T′. This implies that T′ is a covering matrix space. Indeed, for x∈U, (kerμx)∩T′=kerμx=0, while for x∈/U we have dimμx≥2, so that (kerμx)∩T′=0 by computing dimensions. However, this is a contradiction as T is minimal.
Now we may choose x1,x2,…,xn∈U and τ1,τ2,…,τn∈T in such a way that kerμxi=Rτi and τi form a basis of T. Let us complete x1,…,xn to a sequence x1,…,xd which spans X. Put yij=τi(xj). It is clear that yij span the vector space generated by the columns of all matrices in T. We claim that the subset {yij:i>j} is enough to span this space, which clearly implies that δ(T)⩽(2n).
We have yii=0. So it is enough to show that every yij with i<j can be expressed as a linear combination of yki, k=1,…,n. This follows from the following lemma:
Lemma. For every x0∈U, 0=τ0∈kerμx0 and x∈X, there exists a τ∈T such that τ0(x)=τ(x0).
Proof. The operator μx0 has rank n−1, which implies that for small ε the operator μx0+εx also has rank n−1. Therefore one can produce a rational function τ(ε) with values in T such that mx0+εx(τ(ε))=0. Taking the derivative at ε=0 gives μx0(τ0)+μx(τ′(0))=0. Therefore τ=−τ′(0) satisfies the desired property.
Remark. Lemma in solution 2 is the same as the claim ImA⊂V at the beginning of solution 1, but the proof given here is different. It can be shown that all minimal covering spaces T with dimT=(2n) are essentially the ones described in our example.
Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 3–4. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.
Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.
Πώς πήγε;
Οι κινήσεις που σημειώνεις επιστρέφουν νωρίτερα στη διαλογή.