The question was given in the early chapters of Linear Algebra by Hoffman & Kunze, so I am trying to give a proof with only the tools given to me so far - which are mainly row reduction and knowledge of matrix multiplication, row reduced echelon forms, row equivalence and linear independence.

I attempted a proof as per the following:

Consider $A$ as a collection (not sure if this would be the ideal expression) of $1 \times n$ row vectors, and $B$ as a collection of $n \times 1$ column vectors. Then we have that:

$$ A=\begin{bmatrix} r_1 \\ \vdots \\ r_m \end{bmatrix},\ B=\begin{bmatrix} c_1 & \cdots & c_m \end{bmatrix}. $$ Thus it follows that: $$ AB =\begin{bmatrix} r_1\cdot c_1 & \cdots & r_1\cdot c_m \\ \vdots & ~ & \vdots \\ r_m\cdot c_1 & \cdots & r_m \cdot c_m \end{bmatrix} $$ Clearly, by inspection, the rows are linearly dependent.

Since the rows of $AB$ are linearly dependent, it naturally follows that the reduced row echelon form of $AB$ contains zero rows. Hence, $AB$ is not invertible.

Would this be a mathematically sufficient proof?

  • 1
    $\begingroup$ no. think about the rank of these matrices or the null space of $B$. $\endgroup$ – user251257 Aug 4 '15 at 7:50
  • $\begingroup$ @user251257 Although I am aware of the notion of rank and its definition, I am trying to do a proof that is sufficient with only the knowledge of row reduced echelon matrices, elementary row operations, and matrix multiplication. I will edit that in to the original post. $\endgroup$ – user245273 Aug 4 '15 at 7:53
  • $\begingroup$ the problem is the word clearly. not row echelon form. how do you see that the rows are linearly dependent? $\endgroup$ – user251257 Aug 4 '15 at 7:56
  • 2
    $\begingroup$ One reason to learn about linear maps: Solve these problems without any effort in one line. In my opinion, matrices are really the main source of confusion in linear algebra. Perhaps one should ignore books who put a great emphasis on matrices before treating linear maps, because this makes everything more complicated as it is. $\endgroup$ – Martin Brandenburg Aug 4 '15 at 7:57
  • $\begingroup$ @user251257 If you take any two arbitrary rows from $AB$, are they not scalar multiples of one another? $\endgroup$ – user245273 Aug 4 '15 at 7:58

Here's a proof that relies on matrix multiplication.

We can adjoin $m-n$ columns of zeros to $A$ and $m-n$ rows of zeros to $B$ to form $m\times m$ matrices $A', B'$. This won't affect the product $AB$, meaning $A'B'=AB$.

Then we'll have something like

$$ \left[\begin{array}{c|c} A & 0 \end{array} \right] \left[\begin{array}{c} B\\ \hline 0 \end{array}\right]=A'B'$$

Since $A'$ has a column of zeros, $\det A'=0$, so $\det{A'B'}=0$ .

But since $AB=A'B'$, we have $\det{AB}=\det{A'B'}=0$, which means that $AB$ is not invertible.

  • $\begingroup$ What an ingenious solution! $\endgroup$ – user245273 Aug 5 '15 at 16:48
  • $\begingroup$ Thanks! It's how my algebra teacher proved it in class :) $\endgroup$ – coldnumber Aug 5 '15 at 17:03

As has been mentioned in the comments, your approach does not make a for complete and proper proof. You may proceed as follows:

We have from here, for example, that $\operatorname{rank}(AB) \leq \operatorname{min}(\operatorname{rank}(A), \operatorname{rank}(B))$. This you could try to prove using the tools you already know.

In your problem we have that $\operatorname{rank}(A)\leq n$ and $\operatorname{rank}(B)\leq n$ implying that $\operatorname{rank}(AB) \leq n$, but $AB$ is $m$ by $m$ with $n<m$ hence $AB$ can not have full rank which in turn means that it is not invertible.

  • $\begingroup$ Thank you! I think I understand the nature of the proof abstractly as well, now. $\endgroup$ – user245273 Aug 4 '15 at 8:16
  • $\begingroup$ you are welcome :-) I corrected the typo, thanks for being careful :-) $\endgroup$ – Math-fun Aug 4 '15 at 8:18

Your Answer

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