0
$\begingroup$

How many distinct (if matrix $M$ is included in count, do not include $PM$ where $P$ is permutation matrix) $3\times 3$ matrices with entries in $\{0,1\}$ are there such that each row is non-zero, distinct and such that each matrix is of real rank $2$ or $3$?

I think answer for rank $2$ is $6$, for rank $3$ is $29$.

$\endgroup$
  • $\begingroup$ Can you expound upon what permutational equivalence means? Something along the lines of: "matrices $A$ and $B$ are equivalent iff ..." $\endgroup$ – Sammy Black Apr 10 '15 at 5:34
  • $\begingroup$ Specifically, are you permuting all $9$ entries arbitrarily or just the $3$ columns or ... ? $\endgroup$ – Sammy Black Apr 10 '15 at 5:36
  • $\begingroup$ Clarified question. $\endgroup$ – Turbo Apr 10 '15 at 5:41
  • $\begingroup$ Sorry, I'm still not quite sure what you're asking. When you say "do not count...", do you mean if two matrices are equivalent by permuting rows, then count the equivalence class just once? $\endgroup$ – Sammy Black Apr 10 '15 at 5:46
  • $\begingroup$ "if two matrices are equivalent by permuting rows, then count the equivalence class just once" correct. $\endgroup$ – Turbo Apr 10 '15 at 6:00
2
$\begingroup$

In the following, I'm endowing the set $\{0, 1\}$ with the operations of addition and multiplication modulo $2$ (e.g. $1 + 1 = 0$), and this ring is usually denoted $\Bbb{Z}_2$ (or $\Bbb{F}_2$ if we're emphasizing the fact that it's a field.)

Rank $3$: These are full rank matrices, so the conditions that the rows are nonzero and distinct are guaranteed. If a matrix has $3$ distinct rows, then all $6 = 3!$ permutations of the rows will be distinct matrices. So counting all full rank $3 \times 3$ matrices with entries in $\{0, 1\}$ will overcount by a factor of $6$.

Here's how it goes:

  • The only restriction on the first row (thinking of it as a vector in $\{0, 1\}^3$ is that it cannot be $\mathbf{0}$, so there are $2^3-1$ possibilities. Call this row $\mathbf{v}_1$.
  • For the second row, it cannot be either of the $2$ multiples of $\mathbf{v}_1$, namely $\mathbf{0} = 0\mathbf{v}_1$ or $\mathbf{v}_1 = 1\mathbf{v}_1$. So there are $2^3-2$ possibilities. Call this row $\mathbf{v}_2$.
  • For the third row, it cannot be any linear combination of $\mathbf{v}_1$ and $\mathbf{v}_2$. There are $2^2=4$ of these. So there are $2^3-4$ possibilities of this third row. Call it $\mathbf{v}_3$.

Hopefully, you see the pattern here (so you could solve this problem for $n \ne 3$ as well). There are

$(2^3-1)(2^3-2)(2^3-2^2) = 7 \cdot 6 \cdot 4 = 168$ distinct matrices,

and up to permutation of the rows, there are

$\dfrac{168}{6} = 28$ possibilities.


Rank $2$: In this case, since you are only counting matrices up to permutation of the rows and since the rows are distinct and nonzero, you might as well assume that the last row is the sum of the first two. (Do you see why?)

There are $2^2=4$ possible linear combinations of the first two rows that could product the last row: choose either coefficient $0$ or $1$ independently for each of $\mathbf{v}_1$ and $\mathbf{v}_2$. However, both $\mathbf{v}_3 = 1\mathbf{v}_1 + 0\mathbf{v}_2 = \mathbf{v}_1$ and $\mathbf{v}_3 = 0\mathbf{v}_1 + 1\mathbf{v}_2 = \mathbf{v}_2$ produce a row identical to a previous one and $\mathbf{v}_3 = 0\mathbf{v}_1 + 0\mathbf{v}_2 = \mathbf{0}$, which is also not allowed. Hence, the third row must be $\mathbf{v}_3 = 1\mathbf{v}_1 + 1\mathbf{v}_2$

The first row has $2^3 - 1$ possibilities, and the second row has $2^3 - 2$ possibilities. Now there are

$(2^3-1)(2^3-2)(1) = 7 \cdot 6 \cdot 1 = 42$ distinct matrices,

and up to permutation of the rows, there are

$\dfrac{42}{6} = 7$ possibilities.

$\endgroup$
  • $\begingroup$ You are getting one more than me which is strange. $\endgroup$ – Turbo Apr 10 '15 at 13:44
  • $\begingroup$ Could you list rank $2$ matrices? $\endgroup$ – Turbo Apr 10 '15 at 13:47
  • $\begingroup$ [111;110;001], [111;101;010], [111;011;100], [110;100;010], [101;100;001], [011;010;001] what is 7th matrix? Your count is somewhere wrong. $\endgroup$ – Turbo Apr 10 '15 at 14:24
  • $\begingroup$ You missed [101;110;011]. $\endgroup$ – Sammy Black Apr 10 '15 at 16:57
  • $\begingroup$ dude i am over reals. $\endgroup$ – Turbo Apr 10 '15 at 17:27

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.