# image and invertibility true/false

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.

• Most are not invertible. – André Nicolas Jul 13 '16 at 3:55
• By image, do mean image of the whole $m$-dimensional space under the linear transformation $A$ (and similarly $B$)? – Mark Fischler Jul 13 '16 at 3:55

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.

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.