0
$\begingroup$

Could someone please tell me whether or not these two statements are true, I would like to check my answers, but these two are not in the back of the book!

  1. If A and B are n x m matrices such that the image of A is a subset of the image of B, then there must exist an m x m matrix C such that A=BC.

  2. Among the 3x3 matrices whose entries are all zeros and ones, most are invertible.

$\endgroup$
  • 3
    $\begingroup$ Since you are checking your answers, please update your post with your work. $\endgroup$ – Alex Wertheim Jul 13 '16 at 3:47
  • $\begingroup$ Most are not invertible. $\endgroup$ – André Nicolas Jul 13 '16 at 3:55
  • $\begingroup$ By image, do mean image of the whole $m$-dimensional space under the linear transformation $A$ (and similarly $B$)? $\endgroup$ – Mark Fischler Jul 13 '16 at 3:55
1
$\begingroup$

We only show that fewer than half are invertible.

There are $7$ choices for the first row, for we must avoid choosing all $0$'s.

For each of these choices, there are $6$ choices for the second row, for we must avoid choosing all $0$'s, and also must avoid the first row.

For each of these choices, there are never more than $5$ choices for the third row, for we must avoid choosing all $0$'s, and also must avoid the first two rows.

Thus the total of invertibles is no more than $210$, while there are $2^9=512$ matrices in total.

Remark: The total number of invertibles is actually less than $210$, because, for example, we cannot have the third row equal to the sum of the first two.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

For the first question, apply $A$ to all canonical basis vectors; the images are in the image of $B$, so you can find preimages that $B$ sends to these images; choose $C$ so that it sends the canonical basis vectors to these preimages.

For the second question (please in future post one question or set of related questions at a time), we can count the matrices without a zero row or column by inclusion-exclusion:

\begin{align} \sum_{j=0}^3\sum_{k=0}^3(-1)^{j+k}\binom3j\binom3k2^{jk} &= \sum_{j=0}^3(-1)^j\binom3j\left(1-2^j\right)^3 \\ &= 0+3-81+343 \\ &= 265\;. \end{align}

Of these, $3\cdot6=18$ have two identical rows that are not all $0$ or all $1$ and a third row that's the complement of those two (so that none of the columns are zero); these are also not invertible. That leaves at most $265-18=247$ invertible matrices, and thus less than half.

| cite | improve this answer | |
$\endgroup$

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.