Two introductory linear algebra problems

Question

I remember when I was in Moscow one of my homework questions was:

Is there a $2\times 4$ matrix whose $2\times 2$ minors are:

a) $(2,3,4,5,6,7)$

b) $(3,4,5,6,7,8)$

c) $(5,6,7,8,9,10)$

This problem is supposed to be an easy application of some basic result in multilinear algebra, but I still do not know how to solve it. I also want to ask the question for $n\times m$ matrix and $n\times n$ minors in general, for which we will have $\displaystyle C^{m}_{n}=\frac{m!}{n!(m-n)!}$ numbers to choose. I only know this is somehow related to intersection varieties, but the problem is really tiny, so there should be some easy solution of it.

The second problem, which appeared in my last year's final, was this:

Let $A$ and $B$ be two matrices with $m$ rows and $n\ge m$ columns. Prove that $$\det(AB^{t})=\sum_{I}\det A_{I} \det B_{I},$$ where the sum is running over all increasing sequences $I=(i_{1},i_{2},\dots,i_{m})\subset (1,2,\dots,n)$ and $A_{I},B_{I}$ mean $m\times m$-submatrices formed by $I$-columns.

This problem gives me the same feeling that it is supposed to be elementary and solvable by simple tools, but I could not unravel it via standard tools available. I feel there must be some better way to do it than expanding right side to equal the left side, etc. It has been one year and I still do not know how to solve it; so I decided to ask in here. This is from past exam so I think it is ok to ask online now.

Answer 1

For the second question, the formula is called the Cauchy-Binet formula, and the wikipedia page has a proof.

---

A higher level perspective which indicates how one might actually derive the formula is the following. Given a linear map $A:V\to V$, what is $\det(V)$? If we wedge $A$ together with itself $\dim V$ many times, we get a linear map $\bigwedge^{\dim V} A: \bigwedge^{\dim V}V\to \bigwedge^{\dim V}V$. However, since $\bigwedge^{\dim V}V$ is a one dimensional vector space, this map must be multiplication by a scalar. This scalar is $\det(A)$.

Because $V\mapsto \bigwedge^k V$ is functorial, if we have two linear transformations $A,B:V\to V$, we have that $\bigwedge^{\dim V} (AB)=(\bigwedge^{\dim V} A)(\bigwedge^{\dim V} B)$, and hence $\det(AB)=\det A \det B$.

What if we have a linear maps $A:V\to W$ and $B:W\to V$, and we want to compute $\det(BA)$? By functoriality, we have $\det(BA)=\bigwedge^{\dim V}(BA)=(\bigwedge^{\dim V} B)(\bigwedge^{\dim V} A)$. Thus, we need to understand $\bigwedge^{\dim V} B$ and $\bigwedge^{\dim V} A$.

Let $\dim V = m$ and $\dim W=n$ with $m\leq n$, and fix a basis of $V$ and $W$ so that $A$ and $B$ are given as matrices. Then we have a basis for $\bigwedge^{\dim V} W$ given by taking wedges of $m$ basis vectors of $W$, which is in correspondence with $m$ element subsets of $[n]=\{1,2,\ldots, n\}$. If $S\subset [n]$, we let $w_S$ be the corresponding basis vector. The coordinate of $\bigwedge^{\dim V} A$ corresponding to $w_S$ is exactly the minor coming from taking the columns from the set $S$. Something entirely similar happens with $B$.

We are left with two transformations $\mathbb{F}\to \mathbb{F}^{\binom{n}{m}} \to \mathbb{F}$, and we have that the coordinates of the transformations correspond to minors. Calculating the composition gives the formula.

---

For the first question, while Luboš Motl has already provided a good answer, there is some additional context to had. The map that sends an $m \times n$ matrix to it's minors is a form of the Plücker embedding, which embeds Grassmannians inside of projective space (and in particular shows that the Grassmannian is a projective variety).

Your particular case, which parameterized lines in $P^3$, is the prototypical example, and it is a classical result that the embedding is defined by a single quadratic relation (see the wikipedia page. The problem you have is to determine which of those particular points are on the quadric defined by the embedding.

If I had to guess, I would say that this is why you were assigned the problem and what you were supposed to get out of it.

Answer 2

The second question can be simply answered via differential forms. Concider linear maps $f(x)=B^t x$, $g(y)=Ay$, $z=f(y(x))$. Then the volume $m$-form $w=dz_1\wedge dz_m$ of can be written out as the rhs in question. Lhs can be regarded as volume dilatation coefficient of the resulting map $f\circ g$. Without differential forms this proof can be viewed sort of "volume of the image of a unit cube after $f\circ g:\mathbb R^m\to\mathbb R^n\to \mathbb R^m$ is equal to the sum corresponding to all oriented projections $P_L g$ of mappings $\mathbb R^m$ into $m$-dimentional coordinate subspaces $L\subset \mathbb R^n$: $f\circ g=\sum_L f\circ P_L g$."

Answer 3

Privět, concerning the first problem, the minors don't change if the two 4-component rows of the $2 \times 4$ matrix are being subtracted from each other (like if you solve a set of linear equations) - because the 6 entries are really the components of a wedge products of the two 4-dimensional rows. In particular, without changing the minors, I can always bring the matrix to the form $$\begin{array}{ccc} e&0&a&b\\0&1&c&d\end{array}$$ The minors are then $e,ec,ed,-a,+b,ad-bc$. Note that I only have five parameters $a,b,c,d,e$ now to adjust six minors in your list. How do you figure out whether the six numbers may be written in this form? Note that in my list, once again, $$e,ec,ed,-a,+b,ad-bc$$ it's true that the last 6th entry multiplied the 1st one is equal to minus (the 4th times 3rd plus 5th times 2nd), $e(ad-bc)$. This formula looks unnatural but it must be possible to order the six minors as $A,B,C,D,E,F$ so that $$AB+CD+EF=0.$$ This is a nicely symmetric formula and there must exist a more covariant way to derive it, without putting zeros at some random places haha. Oh, I actually know how to derive the formula in a simple way. The 6 minors are the components of the wedge product $W = r_1\wedge r_2$ which belongs to a plane, so its wedge-square - a 4-form - has to vanish. Then it's enough to collect the coefficients in front of $e_1\wedge e_2\wedge e_3\wedge e_4$ of $W\wedge W$ - note that the latter doesn't vanish identically because they're two even 2-forms so the wedge product is symmetric. This coefficient will obviously look like $AB+CD+EF$.

At any rate, the equation above clearly can't be satisfied with positive minors. However, I am confident that with other positions of the zeros, and/or conventions for the signs of the minors, you may flip some signs in the equation above (two sign flips are equivalent to one - it's the only form of the equation inequivalent to the three identical terms), to get $$AB+CD=EF$$ In this form, it's straightforward to test the permutations of your three lists of minors. The possible values of $AB+CD-EF$, using all possible permutations of the six minors $A,B,C,D,E,F$, in the three cases are:

{-20, -19, -16, -11, -9, -5, -4, -1, 0, 4, 5, 7, 8, 11, 12, 13, 16, 17, 20, 23, 24, 25, 28, 29, 31, 32, 35, 36, 40, 43, 44, 45, 49, 52, 53, 56}

{-18, -17, -14, -7, -5, -1, 2, 5, 6, 10, 13, 14, 15, 19, 21, 22, 23, 25, 26, 30, 34, 35, 37, 38, 41, 43, 46, 47, 49, 50, 54, 58, 59, 61, 65, 70, 71, 74}

{-8, -7, -4, 7, 9, 13, 20, 23, 24, 28, 32, 35, 37, 41, 43, 47, 48, 49, 52, 56, 60, 61, 64, 65, 67, 71, 73, 77, 80, 83, 84, 88, 92, 97, 99, 103, 112, 113, 116}

Note that zero is only found in the first case, so only $(2,3,4,5,6,7)$ can be produced as minors of such a matrix. The Mathematica code I used:

a = {2, 3, 4, 5, 6, 7} + p {1, 1, 1, 1, 1, 1};
f[v_] := v[[1]]*v[[2]] + v[[3]]*v[[4]] - v[[5]]*v[[6]];
b = Permutations[a];
Union[Map[f, b] /. {p -> 0}]
Union[Map[f, b] /. {p -> 1}]
Union[Map[f, b] /. {p -> 3}]

If I extend the function $f$ above to

f[v_] := {v, v[[1]]*v[[2]] + v[[3]]*v[[4]] - v[[5]]*v[[6]]};

then the results will also show me the right permutation that produced zero: $$ 2\times 5 + 3\times 6 - 4\times 7 = 0.$$ Then it's straightforward to write down a matrix that has the right minors $$\begin{array}{ccc} 2&0&1&-3/2\\0&2&3&5/2\end{array}$$ The subdeterminants are $4,6,5,-2,3,7$ for the pairs of columns $12,13,14,23,24,34$.