How to prove that the rank of a matrix is a lower semi-continuous function?

Question

I need to prove that rank($\mathrm{A}$) is not continuous everywhere but is lower semi-continuous everywhere, where $\mathrm{A}\in \mathbb{C}^{n\times m} $

Answer 1

We have to show the set $S = \{A \in \mathbb{C}^{m \times n} : \texttt{rank}(A) > r \} \tag{1}$ is open for all real $r.$

We need the following fact : given a matrix $A_0 = (a_{ij}^{0})$ of rank $r_0$ there is a $\delta > 0$ such that for any matrix $A=(a_{ij})$ with $\|A - A_0\|_{\texttt{max}} < \delta$ (i,e., $ |a_{ij} - a^0_{ij}| < \delta\ \forall i,j$) we have $\texttt{rank}(A) \geq r_0.$

The proof of this is straightforward, if $r_0 = 0$ the result is immediate, if $r_0 > 0$ there is a $r_0 \times r_0$ non-singular submatrix in $A_0$, call this submatrix $A^{r_0}_0$. We have $\texttt{det}(A_0^{r^0}) \neq 0.$ By continuity of determinant there is a $\delta > 0$ such that for any $r_0 \times r_0$ matrix $B$ with $\|A_0^{r^0} - B\|_{\texttt{max}} < \delta$ we have $\texttt{det}(B) \neq 0.$ So if $A$ is any matrix with $\|A - A_0\|_{\texttt{max}} < \delta$ and $A^{r^0}$ is the submatrix of $A$ with the same indices that determine $A_0^{r^0}$ then $\|A^{r^0} - A_0^{r^0}\|_{\texttt{max}} \leq \|A-A_0\|_{\texttt{max}} < \delta$ which implies $\texttt{det}(A^{r^0}) \neq 0$ so $\texttt{rank}(A) \geq r_0.$

Now we can easily prove $(1)$. If $S$ is non-empty choose $A_0 \in S$ we have $\texttt{rank}(A_0) > r$. We can find $\delta > 0$ such that for any $A$ with $\|A-A_0\|_{\texttt{max}} < \delta$ we have $\texttt{rank}(A) \geq \texttt{rank}(A_0) > r$, so $A \in S$ and $S$ is open.

It is easy to see rank is not a continuous function : each element in the sequence of matrices $\begin{pmatrix} \dfrac{1}{n} & 0 \\ 0 & \dfrac{1}{n} \end{pmatrix}$ has rank 2, but the limit has rank 0.

Answer 2

Let $A\in{\mathbb C}^{n×m}$; we use the symbol $m$ to denote a square minor (a selection of $k$ rows and $k$ columns). For any minor $m$ of the matrix define a function $f_m:{\mathbb C}^{n×m}\to {\mathbb R}$ in this way: if the minor is invertible then $f_m(A) = k$ otherwise $f_m(A) = 0$. Obviously $f_m$ is lower semicontinuous. The rank is the maximum of all $f_m$, for all possible choices of $m$ (including all possible choices of $k$), so it is lower semicontinuous.