Can affine transformation of a matrix changes its rank?

Question

I am exploring several ways to lower the rank of a matrix by preserving set of constraints. I am sure that performing positive affine transformation (f(x) = ax + b, where a is a non-zero value) preserves my set of constraints, but I want to determine if positive affine transformation can lower the rank of a matrix?

Answer 1

I think I understand the problem now. The question is somewhat "artificial" in the context of matrices, so the answer is long, and probably not very fruitful, but I've gone through the logic. I'll present here a TL;DR, and you can read onwards if you want to see the path of the logic.

Suppose $M$ is an $m \times n$ matrix. If the vectors in $\mathbb{R}^m$ and $\mathbb{R}^n$, both containing only $1$ as entries, lie in the column/row spaces of $M$ respectively, then for all $b \neq 0$, there exists an $a \neq 0$ such that applying $f(x) = ax + b$ to the entries of $M$ will reduce the rank by exactly $1$.

Unless we allow $a = 0$, there are no other conditions under which $f(x) = ax + b$ will reduce the rank of $M$.

---

Let's suppose we have a matrix $$M = \left(v_1 | v_2 | \ldots | v_n \right),$$ where $v_1, \ldots, v_n$ are column vectors of $M$. If we take an affine function $$f : \mathbb{R} \to \mathbb{R} : x \mapsto ax + b,$$ then applying $f$ to the entries of $M$ corresponds to the matrix $aM + bJ$, where $J$ is the matrix of appropriate dimensions whose entries are all $1$. In particular, if we let $j = (b, b, \ldots, b)^T$, we get the matrix, $$aM + bJ = \left(av_1 + j | av_2 + j | \ldots | av_n + j \right).$$ Let's first acknowledge that $b = 0$ is a waste of time; the matrix's rank will be perfectly preserved.

To find the rank of $aM + bJ$, we compute its nullity, comparing to the nullity of $M$. So, let's suppose we have $v = (c_1, c_2, \ldots, c_n)^T$ such that $(aM + bJ)v = 0$. Then we have, \begin{align*} c_1 (av_1 + j) + \ldots + c_n (av_n + j) &= 0 \\ c_1 v_1 + \ldots + c_n v_n &= -\frac{c_1 + \ldots + c_n}{a}j. \end{align*} Now, consider two possibilities: either $j$ is in the columnspace of $M$ or it isn't. If it isn't, then the above equation must have $c_1 + c_2 + \ldots + c_n = 0$. This may or may not increase the rank of $M$ by $1$, as it adds an extra constraint on the nullspace of $M$. This depends on whether or not the vector $(1, 1, \ldots, 1) \in \mathbb{R}^n$ is in the rowspace of $M$.

Note: there's no way, in the case of $j$ not being in the columnspace of $M$, that we can ever reduce the rank of $M$. Also, the (non-zero) value of $b$ is immaterial. We are really just testing whether $j/b = (1, 1, \ldots, 1)^T$ belongs to the columnspace of $M$. This already gives us a constraint as to when this technique could be useful to you.

The other possibility is that $j$ (or equivalently, $j/b$) is in the columnspace of $M$. In this case, we can write, $$j = d_1 v_1 + \ldots + d_n v_n,$$ for some $d_1, \ldots, d_n$. Let $w = (d_1, \ldots, d_n)^T$, and $N = (w | w | \ldots | w) \in \mathbb{R}^{n \times n}$. Note that we have $j = Mw$ and $bJ = MN$. We therefore have, $$aM + bJ = aM + MN = M(aI_n + N).$$ Let's consider the eigenvalues of $N$. Since $w \neq 0$, it is rank $1$. There are two possibilities: either $d_1 + \ldots + d_n = 0$ or not. If it is equal to $0$, it's not difficult to check that $N^2 = 0$, hence $0$ is the only eigenvalue of $N$. Therefore, $aI_n + N$ will have $a \neq 0$ as its only eigenvalue, hence is invertible, and so $aM + bJ$ will have the same rank as $M$.

If it's not equal to $0$, then $w$ is an eigenvector with non-zero eigenvalue $\lambda = d_1 + \ldots + d_n$, and it is the only eigenvalue that is non-zero. Thus, the eigenvalues of $aI_n + N$ are $a$ with multiplicity $n - 1$ and $a + \lambda$ with multiplicity $1$. If $a + \lambda \neq 0$, again, $N$ is invertible, hence $aM + bJ$ will have the same rank as $M$. Hence, we now assume that $$a = -\lambda = -(d_1 + d_2 + \ldots + d_n).$$ Note that $N$ is diagonalisable, hence so is $aI_n + N$ and $(aI_n + N)^T = aI_n + N^T$. Using a classical result, the columnspace of $aI_n + N$ will be the perpendicular complement of the nullspace of $aI_n + N^T$, which simple computation reveals to be $V = (\operatorname{span} (1, 1, \ldots, 1))^\perp$.

Consider the map $x \to Mx$, when restricted to $V$. The nullspace of this map is the subspace of all vectors in $V$ that map to $0$, which is clearly $\operatorname{null} M \cap V$, a subspace of $\operatorname{null} M$. Thus, the nullity of the restricted map is less than or equal to the nullity of the unrestricted map. However, the nullity can only differ by at most $1$, as $\operatorname{dim} V = n - 1$. So the nullity of the restricted map is $\operatorname{nullity} M$ or $\operatorname{nullity} M - 1$.

Since $aI_n + N$ is diagonalisable, we can choose a basis of eigenvalues, starting with $w$: $w, w_1, \ldots, w_{n - 1}$. Since $w_1, \ldots, w_{n - 1}$ correspond to non-zero eigenvalue $a$, it follows that their span is the columnspace of $aI_n + N$, i.e. $V$. We can use this to show that $\operatorname{span} (w) \oplus (\operatorname{null} M \cap V)$ is the nullspace of $aM + bJ$. Hence, taking the dimension of each side, we see that we're only interested in the case where the nullity of the restricted map is equal to the nullity of $M$. In this case, we get $$\operatorname{nullity}(aM + bJ) = \operatorname{nullity}(M) + 1 \implies \operatorname{rank}(aM + bJ) = \operatorname{rank}(M) - 1,$$ that is, a decrease in rank, and only by the value $1$.

These nullities are equal, i.e. we obtain a decrease in rank, if and only if \begin{align*} &\operatorname{null} M \cap V = \operatorname{null} M \\ \iff &\operatorname{null} M \subseteq V \\ \iff &(\operatorname{colspace} M^T)^\perp \subseteq V \\ \iff &(\operatorname{rowspace} M)^\perp \subseteq (\operatorname{span}(1,1, \ldots, 1))^\perp \\ \iff &\operatorname{rowspace} M \supseteq \operatorname{span}(1,1, \ldots, 1) \\ \iff &(1, 1, \ldots, 1) \in \operatorname{rowspace} M. \end{align*}

This finally proves the TL;DR above.

---

To cement this, I thought I'd try a few examples. Suppose $$M = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \end{pmatrix}.$$ Note that $M$ satisfies the conditions, and has rank $2$.

Choose $b = 2$. Our value of $a$ is forced to be $-4$, since we can form $2\begin{pmatrix} 1 \\ 1 \end{pmatrix}$ by $2$ lots of the first column vector, and a total of $2$ lots of the second and third vectors. So, we let $f(x) = 2 - 4x$. Applying $f$ to $M$ yields, $$\begin{pmatrix} -2 & 2 & 2 \\ 2 & -2 & -2 \end{pmatrix},$$ which is rank $1$, as predicted.

If we take $$M' = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix},$$ then the conditions are no longer satisfied. The rank is still $2$. If we take $f(x) = 2 - 4x$ as above, and apply to the entries of $M$, then we get $$\begin{pmatrix} -2 & 2 & -2 \\ 2 & -2 & -2 \end{pmatrix},$$ which is still rank $2$.