# Find rank for this special block matrix

$$\Lambda = \begin{bmatrix} I & -(I+B) & 0 \\ 0 & I & -(I+B) \\ A & 0 & 0 \\ 0 & A & 0 \\ 0 & 0 & A \end{bmatrix} = \begin{bmatrix} \Gamma \\ \Xi \end{bmatrix} \in \mathbb{R}^{ (3n+2m) \times 3m}$$ where $$\Gamma = \begin{bmatrix} I & -(I+B) & 0 \\ 0 & I & -(I+B) \end{bmatrix}$$ $$\Xi = \begin{bmatrix} A & 0 & 0 \\ 0 & A & 0 \\ 0 & 0 & A \end{bmatrix}$$

where $B \in \mathbb{R}^{m \times m }$ but not going to be $-I$. Note that $I \in \mathbb{R}^{m \times m }$ and $A \in \mathbb{R}^{ n \times m}$.

My Observations:

1. Let's look at the first two block rows of $\Lambda$, denote as $\Gamma \in \mathbb{R}^{2m \times 3m}$. It is clearly that $rank(\Gamma) = 2m$ and it is full rank in row.
2. The remaining block is a block diagonal matrix of which rank is surely $3 rank(A)$

My derivation on lower bound:

Consider $\Lambda$ being placed as $$\begin{bmatrix} I & -(I+B) & 0 \\ 0 & I & -(I+B) \\ A & 0 & 0 \\ 0 & A & 0 \\ 0 & 0 & A \end{bmatrix}$$ then following the theorem on the lower bound of upper triangular block matrix, we have $$rank(\Lambda) \ge rank(\begin{bmatrix} I \\ A \end{bmatrix}) + 2 rank(A) = m + 2 rank(A)$$

However, if we switch the row, as it is not affecting the rank, we have

$$\begin{bmatrix} I & -(I+B) & 0 \\ A & 0 & 0 \\ 0 & I & -(I+B) \\ 0 & A & 0 \\ 0 & 0 & A \end{bmatrix}$$ We will have $$rank(\Lambda) \ge 2rank(\begin{bmatrix} I \\ A \end{bmatrix}) + rank(A) = 2m + rank(A)$$

Therefore, $$rank(\Lambda) \ge \max\{2m + rank(A) , m + 2rank(A) \}$$

My guess:

Note!! if $n<m$, this guess does not seems to be holding anymore, but $n>m$ it seems to be true

I guess $$rank(\Lambda) = \min \{2m + 3rank (A), 3m\}$$

My result on final: Thanks to the help from @Omnomnomnom

Based on the transformation provided by @Omnomnomnom, the problem now becomes to determine the rank of $$rank(\begin{pmatrix} A \\ A (I+B) \\ A (I+B)^2 \end{pmatrix})$$.

What is striking is that we can simply do some row operation to get \begin{align} & rank(\begin{pmatrix} A \\ A + AB \\ A(I+2B+B^2) \end{pmatrix}) \\ & = rank(\begin{pmatrix} A \\AB \\ AB^2 \end{pmatrix}) \end{align}

Please note that $B$ is a square matrix and $A$ can be a non-square matrix, $$rank(\begin{pmatrix} A \\AB \\ AB^2 \end{pmatrix})$$, is very similar to the observability matrix in linear system theory, where instead of $AB^2$, power up to $AB^{m-1}$ is considered.

Note that $B^{m}$ is linearly dependent with all $B$ under power of $m$. Indeed, for the problem I am trying to solve, the power can be as large as I want, so not simply power of 2 here.

As far as I know, there is no trick for determining the rank of this matrix in control community. This is perhaps the furthest we can go.

My experiment:

I use Matlab to randomly generating different rank of A and B for some random rank (I guess not important), and it shows my guess looks to be fair.

. Just curious if there is something nice to be derived.

clc
clear
n = 300;
m = 100;

for k = 1:min(m,n)
A = rand(n, k)*rand(k,m);
l = randi(k);
B = rand(m, l)*rand(l,m);
lambda = [eye(m) -(eye(m)+B) zeros(m,m);
zeros(m,m) eye(m) -(eye(m)+B);
A zeros(n,m) zeros(n,m);
zeros(n,m) A zeros(n,m);
zeros(n,m) zeros(n,m) A;];

% disp('&&&&&&&&&&&&&&&&&&&&&&&7')
% disp('check if true =')
check =  rank(lambda) == min(2*m+3*rank(A),3*m);

if check ~= (1==1)
disp('something wrong')
end
end

• Where your guess comes from? What have you tried? – Radek Suchánek Jan 30 '18 at 4:51
• @RadekSuchánek Hi, I just add something. Hope this would be helpful. – ArtificiallyIntelligence Jan 30 '18 at 5:17

We can perform the following block "row-operations": $$\pmatrix{I & -(I+B) & 0 \\ 0 & I & -(I+B) \\ A & 0 & 0 \\ 0 & A & 0 \\ 0 & 0 & A } \leadsto \\ \pmatrix{ I & -(I+B) & 0 \\ 0 & I & -(I+B) \\ 0 & A+AB & 0 \\ 0 & A & 0 \\ 0 & 0 & A } \leadsto\\ \pmatrix{ I & -(I+B) & 0 \\ 0 & I & -(I+B) \\ 0 & 0 & A(I + B)^2 \\ 0 & 0 & A(I + B) \\ 0 & 0 & A }$$ It follows that the rank of this matrix will be exactly equal to $$2m + \operatorname{rank}\pmatrix{A(I + B)^2\\A(I + B) \\ A}$$ If $I+B$ is invertible, we can rewrite this as $$2m + \operatorname{rank}\left[\pmatrix{A(I + B)\\A \\ A(I + B)^{-1}}(I + B)\right] = 2m + \operatorname{rank}\left[\pmatrix{A(I + B)\\A \\ A(I + B)^{-1}}\right]$$ This can certainly be bounded above by $2m + 3 \operatorname{rank}(A)$, but I'm not sure how much better we can do.