# 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? Dec 11, 2012 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. Dec 11, 2012 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. Dec 11, 2012 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? Dec 11, 2012 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). Dec 11, 2012 at 5:11