# Impossibility of continuously picking k independent rows from a rank k matrix

Suppose I have an $n\times n$ real (or complex) matrix of rank $k$, and I want to pick $k$ linearly independent rows from it. I want to do this in a continuous fashion as the matrix varies continuously. I'm being a bit vague here, but I think it doesn't matter, because a colleague tells me that it's a standard fact that no matter how one tries to make this precise, the task is impossible (at least if $2\le k\le n-1$). Unfortunately he can't remember where he read this or how to prove it. Can someone confirm this and supply the missing details?

EDIT: As pointed out by several people, I shouldn't have said "rows" but rather a basis for the row space. Sorry for the confusion.

-
The set of matrices with fixed rank $k$ is connected, and there are finitely many ways to choose $k$ independent rows from it. Isn't this enough? –  Angelo Dec 11 '12 at 4:51
I'm trying to read "pick $k$ linearly independent rows from it" as being more than an $n\choose k$ choice, which would then have to be a constant choice if continuous, but I can't see how to reinterpret in any other way. –  Allen Knutson Dec 11 '12 at 5:13
Your first sentence ends "..I want to pick $k$ linearly independent rows from it". To do this in a continuous fashion it should be constant. That means we should pick the same set of $k$ rows for every matrix (see the connectedness observation by Angelo). But that would be impossible as we can easily construct a rank $k$ matrix with a pre-determined set of $k$ rows linearly dependent. –  P Vanchinathan Dec 11 '12 at 5:41
So, clearly, you can choose a piecewise continuous choice. Is it possible to make choices, so that at each discontinuity, one need to change at most $r$ of the k rows? What is a lower bound on $r$? Is it possible to have that only rows needs to be changed at each discontinuity? –  Per Alexandersson Dec 11 '12 at 9:50

Picking $k$ linearly independent rows is harder than picking a basis for the row space. The row space forms a vector bundle on the manifold of rank $k$ matrices. Picking a basis continuously would be equivalent to picking a trivialization of the vector bundle.

So your colleague's claim is weaker than the fact that the row space vector bundle on that manifold is nontrivial, for $1 \leq k \leq n-1$.

In the real case: Its first Stiefel-Whitney class is nontrivial, because the manifold of rank $k$ matrices is a fiber bundle on the Grassmanian $G_k^n$, and we are just pulling back the tautological bundle. The tautological bundle has all Stiefel-Whitney classes nontrivial, and the fibers of the map are connected, so the pullback of that class is similarly nontrivial

In the complex case: We can make a similar argument with the first Chern class, using the fact that the fibers are simply connected.

-
As Angelo points out, this statement is trivial if by "rows" you mean rows with respect to a fixed basis. A generalization would be to allow the "rows" to come from any basis. Up to some duality, this is equivalent to asking to be able to continuously choose a set of $k$ linearly independent vectors whose span is disjoint from the kernel of your linear map.
Here's a simple way to see you can't do this. The Grassmannian $G_{n,k}$ of $k$-planes in $F^n$ ($F=\mathbb{R}$ or $\mathbb{C}$) embeds in the space of rank $k$ matrices by sending a $k$-plane to the orthogonal projection onto it. If we could continuously choose $k$ linearly independent vectors whose span is disjoint from the kernel of such a projection, then by applying the projection to these vectors we could continuously choose bases for all $k$-planes. That is, we would have a trivialization of the tautological vector bundle on $G_{n,k}$. But the tautological bundle is certainly not trivial if $0<k<n$ (you can use characteristic classes, or use the universal property of the Grassmannian and simply give an example of any nontrivial rank $k$ bundle generated by $n$ sections).
My argument is essentially the same as Will's except instead of using connectedness properties of the fibers of the map from the space of rank $k$ matrices to the Grassmannian, I use a section of that map (given by orthogonal projections). –  Eric Wofsey Dec 11 '12 at 5:11