Assume you are given two full rank matrices with the same number of columns $A$ and $B$. That is, $A$ is $n\times m$, $B$ is $k\times m$, and rank$(A)=n$, rank$(B)=k$ (where we have assumed $n,k\leq m$). Is it possible to determine the dimension of the intersection of their rowspaces?

For me it is tempting to reason as follows: Let $I$ and $J$ be the pivot (see below what I mean) positions of $A$ and $B$ respectively. Does the dimension in question equal to $|I\cap J|$?

By $\textbf{pivot positions}$ I mean the columns in which the identity matrix shows up after necessary row operations.

I am primarily interested on binary matrices, but the question can be asked in any field.

  • $\begingroup$ " two full rank matrices with the same number of columns " ? To me "full rank" means the number of columns and rows are the same? In which case the result is truly elementary. $\endgroup$ – rrogers Aug 13 at 14:07
  • $\begingroup$ @rrogers No, it doesn't mean that. To elaborate, you are given two matrices $n\times m$ and $k\times m$ respectively, each of which is full rank. But I made an edit anyway. $\endgroup$ – user 1987 Aug 13 at 14:22
  • $\begingroup$ I would use exterior products on the rows and compare the subsequent volumes/subspaces. Alternately I think that using Psuedo-inverses can be carried out. $\endgroup$ – rrogers Aug 13 at 14:46
  • $\begingroup$ The advantage of exterior products is that it is a steamroller without any particular decisions about contents. $\endgroup$ – rrogers Aug 13 at 15:29
  • $\begingroup$ By $|I\cap J|$ do you mean rank $(I \cap J)$? $\endgroup$ – Marc Bogaerts Aug 13 at 17:23

Label as $a_k$ the row vectors of $A$ that don't belong to $I \cap J$, $i_l$ the vectors in $I \cap J$ and $b_m$ the vectors of $B$ not in $I \cap J$. Then it is not hard to see that the vectors $a_k, i_l, b_m$ form an lineary independent set. If $v$ is a linear combination of the $i_l$ then it is clear that $v \in \operatorname{span}(A)$ and also $v \in \operatorname{span}(B)$. If on the other hand $v \in \operatorname{span}(A) \cap \operatorname{span}(A)$ then $v = \sum_k \alpha_k a_k + \sum_l \beta_l i_l $ and also $v = \sum_m \gamma_m b_m + \sum_l \delta_l i_l $ for some $\alpha_k, \beta_l, \gamma_m, \delta_l$ from which $\sum_k \alpha_k a_k-\sum_m \gamma_m b_m + \sum_l \beta_l i_l -\sum_l \delta_l i_l = 0$ and, because of linear independency $\alpha_k = \gamma_m = 0$ and $\beta_l = \delta_l$. This shows that the $i_l$ forms a basis of the intersection of the rowspaces and that your assertion about the dimension is correct.

  • $\begingroup$ If you are planning to use your result in the effective calculation of the intersection of two rowspaces then it may be of interest to know that it suffices to make the two matrices "pre"-triangular (with ones on the "pre"-diagonal) instead of going as far as to make row operations to obtain full identity sub matrices. $\endgroup$ – Marc Bogaerts Aug 15 at 12:48

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.