Rank of a matrix subtracted by a vector

Question

I have a matrix $A \in \mathbb{R}^{n\times n}$ whose columns are linearly independent and, thus, $\text{rank}(A)=n$. The Euclidean length of each column is the same, i.e., all columns are normalized and scaled.

I subtract each column of $A$ by a vector $u \in \mathbb{R}^n$. Let us call such a matrix $B$. Can we show that $\text{rank}(B) \geq n-1$ ? If not, then under what conditions is this true?

Answer 1

Since $A$ has rank $n$ its columns form a basis for $\mathbb{R}^n$. Assuming $u\neq 0$, there exists a nonzero vector $x\in\mathbb{R}^n$ such that $u = Ax$. Thus

$$ A - ue^T = A - Axe^T = A(I - xe^T), $$

where $e$ is the $n$-vector of all ones. Since $A$ has rank $n$,

$$ \operatorname{rank}(A-ue^T) = \operatorname{rank}(A(I - xe^T)) = \operatorname{rank}(I - xe^T) $$

So you have to show that $\operatorname{rank}(I - xe^T) \geq n - 1$, or equivalently that the nullspace of $I - xe^T$ has at most dimension one. To do so, suppose that $v$ is a nonzero vector in $\mathbb{R}^n$ that satisfies the equation

$$ (I - xe^T)v = 0 \iff v_i = x_i\sum_{j=1}^n v_j,~~i = 1,\ldots,n $$

which is possible if and only if $e^Tx = 1$. Thus, if $e^Tx = 1$, then the nullspace of $I-xe^T$ is $\operatorname{span}\{x\}$ which has dimension one, otherwise, it is the trivial nullspace $\{0\}$ which has dimension zero.

Answer 2

Suppose that $(e_1,...,e_m)$ are the columns, it is a basis of $\mathbb{R}^n$, consider the matrix $B_1=(e_1-u,e_2,...,e_n)$, if its rank is $n-1$, $u=e_1+a_2e_2+..+a_ne_n$, in this case write $v_1=a_2e_2+..+a_nv$ $(e_1-u,e_2-u,...,e_n-u)=(-v,e_2-e_1-v,...,e_n-e_1-v)$ and the rank of the last matrix is superior to $n-1$ since $(e_2-e_1,...,e_n-e_1)$ is in the vector space generated by $(-v,e_2-e_1-v,...,e_n-e_1-v)$.

If the rank of $B_1$ is $n$, consider the matrix $B_2=(e_1-u,e_2-u,e_3,...,e_n)$ if its rank is $n-1$, $u=e_2+a_1(e_1-u)+a_3e_3+..+a_ne_n$, write $v_2=a_1(e_1-u)+a_3e_3+..+a_ne_n$, $(e_1-u,e_2-u...,e_n-u)=(e_1-u-e_2-v,-v,e_3-e_2-v,...,e_n-e_2-v)$ has rank $n-1$ or $n$.

recursively, you obtain that the rank of $(e_1-u,e_2-u,...,e_n-u)$ is $n-1$ or $n$.