# Rank of a rectangle partitioned matrix with sub-matrices are diagonal matrices

Let $m_i \in \mathbb R^n$ be a vector with elements that are greater or equal $0$, and define the partitioned matrix $S \in \mathbb R^{n \times Nn}$ as $S \triangleq \begin{bmatrix} \mathrm{diag}(m_1)& \ldots& \mathrm{diag}(m_N) \end{bmatrix}$ with $N>1$. Is there a rigorous way to find $\textbf{rank}(S)$?

$\textbf{Observations:}$

1) Since $N>1$, $\textbf{rank}(S) \le n$.

2) Let $\bar{m} \triangleq m_1 + \ldots + m_N \in \mathbb R^n$. Since elements of $m_i$ are greater or equal $0$ for $i=1,\ldots,N$, there is no cancellation that leads to $0$ element on $\bar{m}$. Therefore, the only way to get a $0$ elements in $\bar{m}$ is a zero row in $S$. Hence, \begin{align} \textbf{rank}(S) &= \text{number of positive elements in \bar{m}} \\ &= n - \text{number of 0 elements in \bar{m}}. \end{align} Is there a rigorous way to justify/prove this second observation?

• Yes, there is a rigorous way to prove the second observation. One approach would be to sort the rows of $S$ according to the appearance of a leading nonzero entry. The rank deficiency of $S$ is the count of all zero rows it has. – hardmath Mar 16 '18 at 20:47
• I edited the first observation. Can you be more specific on the sorting method? Thanks. – dt1213 Mar 16 '18 at 20:52

Alternate (but essentially equivalent) approach:

Recall the rank of $S$ is the dimension of its column space. The columns of $S$ are multiples of $e_1, \ldots, e_n$ (the standard basis).

If the first components of each of $m_1, \ldots, m_n$ are all zero, then $e_1$ does not appear in the column space. Otherwise, $e_1$ does appear in the column space. Similar statements can be made for the other components of the $m_j$.

This leads to the conclusion that the column space of $S$ is the span of the $e_i$ such that $(m_j)_i$ (the $i$th component of $m_j$) is nonzero for some $j$, so the rank of $S$ is the number of $e_i$ satisfying the above. If the entries of the $m_j$ are all nonnegative, then this recovers the formula that you have written.

• Yes. The columns of $S$ have at most one nonzero entry, which makes it a bit simpler to think about how "duplicates" crop up in finding the rank. – hardmath Mar 16 '18 at 21:27

The matrix $S$ can be put into row-echelon form by a sequence of operations:

(1) Scale each row to make the leading nonzero entry, if any, equal to $1$. This does not change the form of $S$ as it regards the diagonal blocks since we would divide a particular row of $S$ by a positive value. Call the resulting matrix $S'$. Now every nonzero row of $S'$ has a "leading one".

(2) Sort the resulting rows of $S'$ according to the rows leftmost positions of leading ones. Accordingly any all-zero rows of $S'$ will be sorted to the bottom rows, and we call this sorted matrix $R$. Now $R$ is in row-echelon form.

Noting that $\textbf{rank}(S) = \textbf{rank}(R)$ because these elementary row operations leave rank unchanged, we see that $\textbf{rank}(R)$ is evidently $n$ minus the number of all zero rows in $R$.

But a row in $R$ contains only zeros if and only if the original row in $S$ contained only zeros. Finally, the sum of corresponding entries in the non-negative vectors $m_i$ is zero if and only if all those corresponding entries of vectors $m_i$ are zero, so counting such zero sums is the same as counting the zero rows of $S$. QED