A question about the rank of some matrix

Question

Let $P$ be a $s \times s$ matrix and $Q$ be a $s \times r$. Assume that $\mbox{rank} (P|Q)=s$, can we find a $r \times s$ matrix $R$ such that $\mbox{rank} (P+QR)=s$?

Answer 1

Let $\text{rank}(P)=N$. Let the field for our vector space be $K$. We can regard a $m$-by-$n$ matrix as a function from $K^n$ to $K^m$.

1. If $N=s$, take $R=0_{r\times s}$.

2. If $N=0$, then $P=0$, so that $Q$ has column rank $s$. Let $f_1,\ldots,f_s$ be the standard basis for $K^s$ and $e_1,\ldots,e_r$ be the standard basis for $K^r$. Since $Q$ has column rank $s$, there must be $s$ linearly independent columns among $Q(e_1),\ldots,Q(e_r)$. Therefore $r\geq s$. Let $R$ send $f_i$ to $e_{a_i}$, where $Q(e_{a_1}),\ldots,Q(e_{a_s})$ are linearly independent.

3. If $0<N<s$,

let $g_1,\ldots,g_s$ be a (perhaps non-standard) basis for $K^s$ such that

$\text{Span}\langle P(g_1),\ldots,P(g_N)\rangle=\text{Image}(P)$

and $\text{Span}\langle g_{N+1},\ldots,g_s\rangle=\text{Ker}(P)$.

$Q$ has columns $c_{a_1},\ldots,c_{a_{s-N}}$ such that $\text{Span}\langle P(g_1),\ldots,P(g_N),c_{a_1},\ldots,c_{a_{s-N}}\rangle=K^s$

so $r\geq s-N$.

Let $R$ send $g_1,\ldots,g_N$ to $0$ and let it send $g_{N+1},\ldots,g_s$ to $e_{a_1},\ldots,e_{a_{s-N}}$ respectively,

where once again $\{e_i\}$ is the standard basis for $K^r$.

Answer 2

The answer is yes, as Chris Sander's answer shows. Because of this, it actually follows that for a "randomly selected" $R$ (e.g. if its entries are i.i.d. uniform), $P + QR$ will have full rank.

However, if we want to explicitly construct an example, we can do so as follows. Partition the SVD of $P$ into $$ P = \pmatrix{U_1 & U_2}\pmatrix{\Sigma & 0\\0 & 0}\pmatrix{V_1 & V_2}^T, $$ where $U_1,V_1$ have $\rho = \operatorname{rank}(P)$ columns and $\Sigma$ is $\rho \times \rho$ and diagonal with positive diagonal entries. Then, row-reduce the matrix $[P\ \ Q]$ to get the RREF matrix $$ X = \pmatrix{X_1 &0\\0 & X_2} $$ where $X_1,X_2$ are in RREF and $X_1$ has size $\rho \times s$. Select $a_1,\dots,a_{r}$ such that for each $i$, the $a_i$th column of $X_2$ is a pivot column. Let $J$ be the matrix $[e_{a_1} \cdots e_{a_{r}}]$. That is, let $J$ be the matrix consisting of columns $a_1,\dots,a_{r}$ of the $r\times r$ identity matrix. Then the matrix $$ R = JV_1^T $$ will be such that $P + QR$ has full rank.