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)$?


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?

  • $\begingroup$ 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. $\endgroup$ – hardmath Mar 16 '18 at 20:47
  • $\begingroup$ I edited the first observation. Can you be more specific on the sorting method? Thanks. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.