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).
Original from the official PDF
This transcription was compared symbol by symbol with the original, but not yet by a person.
Time on this problem
Work for at least 45 minutes before opening the solution.
Official solution
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.
Transcribed from the official solutions, pages 3–4. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.