1. Proof involving matrices

Hi,

I was wondering if anyone could help me with this:

Suppose A is a m x n matrix and there exist n x m matrices C and D such that CA = In and AD = Im. Prove that m = n and C = D.

I have never done any proofs in math before , and I don't know where to even start with this. Like, what I did for myself was to give m and n concrete numbers, like make m = 2 and n = 2, and than when I did the "calculations" with a bit more concrete numbers, I see that m = n and C = D, but I am not sure how to "prove this" other than drawing pictures of matrices, and than seeing that C really is = D and Im = In.

Thank you for taking a look at this

2. Re: Proof involving matrices

You should know that when you can only multiply matrices when the number of columns in the first is equal to the number of rows in the second, and the resulting product matrix will have the "remaining" dimensions as its order. So that means \displaystyle \begin{align*} \mathbf{C}_{n \times m} \cdot \mathbf{A}_{m \times n} = \left( \mathbf{CA} \right)_{n \times n} \end{align*}.

Anyway, the idea will be to show that two matrices are equal to the same thing, and are therefore equal to each other. Please note that where I'm using the inverse matrix notation, it means either a right-inverse or a left-inverse, i.e. some matrix which will multiply to give the identity without the original matrix necessarily being square. Working on the first product we have

\displaystyle \begin{align*} \mathbf{C}_{n \times m} \cdot \mathbf{A}_{m \times n} &= \mathbf{I}_n \\ \mathbf{C}^{-1}_{m \times n} \cdot \mathbf{C}_{n \times m} \cdot \mathbf{A}_{m \times n} &= \mathbf{C}^{-1}_{m \times n} \cdot \mathbf{I}_n \\ \mathbf{I}_m \cdot \mathbf{A}_{m \times n} &= \mathbf{C}^{-1}_{m \times n} \\ \mathbf{A}_{m \times n} &= \mathbf{C}^{-1}_{m \times n} \end{align*}

Working on the second product we have

\displaystyle \begin{align*} \mathbf{A}_{m \times n} \cdot \mathbf{D}_{n \times m} &= \mathbf{I}_m \\ \mathbf{A}_{m \times n} \cdot \mathbf{D}_{n \times m} \cdot \mathbf{D}^{-1}_{m \times n} &= \mathbf{I}_m \cdot \mathbf{D}^{-1}_{m \times n} \\ \mathbf{A}_{m \times n} \cdot \mathbf{I}_n &= \mathbf{D}^{-1}_{m \times n} \\ \mathbf{A}_{m \times n} &= \mathbf{D}^{-1}_{m \times n} \end{align*}

So it should be clear therefore that \displaystyle \begin{align*} \mathbf{C}^{-1}_{m \times n} = \mathbf{D}^{-1}_{m \times n} \end{align*}, and so we get

\displaystyle \begin{align*} \mathbf{C}_{n \times m} \cdot \mathbf{C}^{-1}_{m \times n} &= \mathbf{C}_{n \times m} \cdot \mathbf{D}^{-1}_{m \times n} \\ \mathbf{I}_n &= \mathbf{C}_{n \times m} \cdot \mathbf{D}^{-1}_{m \times n} \\ \mathbf{I}_n \cdot \mathbf{D}_{ n \times m} &= \mathbf{C}_{n \times m} \cdot \mathbf{D}^{-1}_{m \times n} \cdot \mathbf{D}_{n \times m} \\ \mathbf{D}_{n \times m} &= \mathbf{C}_{n \times m} \cdot \mathbf{I}_m \\ \mathbf{D}_{n \times m} &= \mathbf{C}_{n \times m} \end{align*}

3. Re: Proof involving matrices

I would look at this more "abstractly". A is a linear transformation that maps $R^m$ to $R^n$. C is a linear transformation that maps $R^n$ to $R^m$ and D is a linear transformation that maps $R^m$ to $R^n$

Now, suppose n> m. Then A maps $R^m$ into an m dimensional subspace of $R^n$. But that means that there exist vector, v, say, in $R^n$ such that $Au\ne v$ for any u in $R^m$. Look at ADv for that v. Do you see that ADv cannot be equal to v?

4. Re: Proof involving matrices

Originally Posted by Nora314
Suppose A is a m x n matrix and there exist n x m matrices C and D such that CA = In and AD = Im. Prove that m = n and C = D.
This is a comment on both replies.

Note that $A$ is a $m\times n$ matrix. Each of $C~\&~D$ is a $n\times m$ matrix.

Usually, as linear transformations, $A:R^n\to R^m,~C:R^m\to R^n,~\&~D:R^m\to R^n$.

Unless we know that $n=m$ we don't think about the inverse of a matrix. There is a notion of right-inverse and left-inverse. But I don't that is called for here.

You are given that $CA=I_n~\&~DA=I_m$ thus
$C=CI_m=C(AD)=(CA)D=I_nD=D$.

How do we get $m=n~?$

5. Re: Proof involving matrices

Originally Posted by Prove It
You should know that when you can only multiply matrices when the number of columns in the first is equal to the number of rows in the second, and the resulting product matrix will have the "remaining" dimensions as its order. So that means \displaystyle \begin{align*} \mathbf{C}_{n \times m} \cdot \mathbf{A}_{m \times n} = \left( \mathbf{CA} \right)_{n \times n} \end{align*}.

Anyway, the idea will be to show that two matrices are equal to the same thing, and are therefore equal to each other. Please note that where I'm using the inverse matrix notation, it means either a right-inverse or a left-inverse, i.e. some matrix which will multiply to give the identity without the original matrix necessarily being square. Working on the first product we have

\displaystyle \begin{align*} \mathbf{C}_{n \times m} \cdot \mathbf{A}_{m \times n} &= \mathbf{I}_n \\ \mathbf{C}^{-1}_{m \times n} \cdot \mathbf{C}_{n \times m} \cdot \mathbf{A}_{m \times n} &= \mathbf{C}^{-1}_{m \times n} \cdot \mathbf{I}_n \\ \mathbf{I}_m \cdot \mathbf{A}_{m \times n} &= \mathbf{C}^{-1}_{m \times n} \\ \mathbf{A}_{m \times n} &= \mathbf{C}^{-1}_{m \times n} \end{align*}

Working on the second product we have

\displaystyle \begin{align*} \mathbf{A}_{m \times n} \cdot \mathbf{D}_{n \times m} &= \mathbf{I}_m \\ \mathbf{A}_{m \times n} \cdot \mathbf{D}_{n \times m} \cdot \mathbf{D}^{-1}_{m \times n} &= \mathbf{I}_m \cdot \mathbf{D}^{-1}_{m \times n} \\ \mathbf{A}_{m \times n} \cdot \mathbf{I}_n &= \mathbf{D}^{-1}_{m \times n} \\ \mathbf{A}_{m \times n} &= \mathbf{D}^{-1}_{m \times n} \end{align*}

So it should be clear therefore that \displaystyle \begin{align*} \mathbf{C}^{-1}_{m \times n} = \mathbf{D}^{-1}_{m \times n} \end{align*}, and so we get

\displaystyle \begin{align*} \mathbf{C}_{n \times m} \cdot \mathbf{C}^{-1}_{m \times n} &= \mathbf{C}_{n \times m} \cdot \mathbf{D}^{-1}_{m \times n} \\ \mathbf{I}_n &= \mathbf{C}_{n \times m} \cdot \mathbf{D}^{-1}_{m \times n} \\ \mathbf{I}_n \cdot \mathbf{D}_{ n \times m} &= \mathbf{C}_{n \times m} \cdot \mathbf{D}^{-1}_{m \times n} \cdot \mathbf{D}_{n \times m} \\ \mathbf{D}_{n \times m} &= \mathbf{C}_{n \times m} \cdot \mathbf{I}_m \\ \mathbf{D}_{n \times m} &= \mathbf{C}_{n \times m} \end{align*}
Wow, thank you so much for the reply this seemed like a nice way to solve the problem!

6. Re: Proof involving matrices

Originally Posted by HallsofIvy
I would look at this more "abstractly". A is a linear transformation that maps $R^m$ to $R^n$. C is a linear transformation that maps $R^n$ to $R^m$ and D is a linear transformation that maps $R^m$ to $R^n$

Now, suppose n> m. Then A maps $R^m$ into an m dimensional subspace of $R^n$. But that means that there exist vector, v, say, in $R^n$ such that $Au\ne v$ for any u in $R^m$. Look at ADv for that v. Do you see that ADv cannot be equal to v?

I think I understand why ADv cannot be equal to v, from what you wrote. It seems to me like ADv cannot be equal to v, because A maps Rm into a subspace, like you said, so that means that it does not cover the whole Rn, it is not "onto"? Therefore there will be a vector v that is left "out", and ADv will never be able to be equal to that vector?

Sorry, I think I am just failing to understand why that proves that C = D?

7. Re: Proof involving matrices

Originally Posted by Plato
This is a comment on both replies.

Note that $A$ is a $m\times n$ matrix. Each of $C~\&~D$ is a $n\times m$ matrix.

Usually, as linear transformations, $A:R^n\to R^m,~C:R^m\to R^n,~\&~D:R^m\to R^n$.

Unless we know that $n=m$ we don't think about the inverse of a matrix. There is a notion of right-inverse and left-inverse. But I don't that is called for here.

You are given that $CA=I_n~\&~DA=I_m$ thus
$C=CI_m=C(AD)=(CA)D=I_nD=D$.

How do we get $m=n~?$
Thank you so so much for the help!

Ok, I understood what you did there

Let me try to do m = n. By trying to do it in a similar way I came up with this:

Im = CC-1 = C(AIn) = CA(In) = In(In) = In

Im = In

Hope that is correct =D I have another question, if you don't mind, you said that A maps Rn into Rm, I thought that it mapped Rm to Rn, since a has m rows and n columns?

8. Re: Proof involving matrices

Originally Posted by Nora314
Let me try to do m = n. By trying to do it in a similar way I came up with this:
Im = CC-1 = C(AIn) = CA(In) = In(In) = In
Im = In
Hope that is correct =D I have another question, if you don't mind, you said that A maps Rn into Rm, I thought that it mapped Rm to Rn, since a has m rows and n columns?
How do you know that $C^{-1}$ exists?

It must be a square matrix. That is what you are trying to prove.

9. Re: Proof involving matrices

Originally Posted by Nora314
if you don't mind, you said that A maps Rn into Rm, I thought that it mapped Rm to Rn, since a has m rows and n columns?
I have waited until now to answer you above question.
Look at this webpage. I did use the word usually.
Most authors, but not all, use the convention of writing the transformation as:
$T\cdot v$ where $T$ is an $m\times n$ matrix and $v$ is a $n \times 1$ column vector yielding a $m \times 1$ column vector.
Hence, it maps $R^n\to R^m$.

Again, be warned this is not an absolute notation.