1

How to prove that a square matrix $A$ is singular if and only if $x\mapsto Ax$ is not injective?

We define the matrix $A$ to be singular if there doesn't exist matrix $A^{-1}$ such that $AA^{-1}=A^{-1}A=I$. Why does it imply that it can map multiple $x$'s to the same value $Ax$? And please don't use of the theorem that says singular matrices have a zero eigenvalue.

Patrick Stevens
  • 36,135
user5539357
  • 349

5 Answers5

3

Equivalently, we would like to show $A$ has an inverse if and only if it is injective. (This is the converse of your original equivalence.)

Suppose $A$ has an inverse. Then $Ax = y$ means $A^{-1} Ax = A^{-1}y$ so $x = A^{-1}y$; so the linear map $A$ is injective.

Suppose $A: \mathbb{F}^n \to \mathbb{F}^n$ is (linear and) injective. Let $\{ e_1, \dots, e_n \}$ be a basis for the vector space $\mathbb{F}^n$. I claim that $A$ is surjective; this is enough, because we can define $A^{-1}(e_i)$ to be the vector $v$ such that $A v = e_i$.

Indeed, $A e_1, \dots, A e_n$ are linearly independent (a dependence between them would be of the form $A(\alpha_1 e_1 + \dots + \alpha_n e_n) = 0$, so $\alpha_1 e_1 + \dots + \alpha_n e_n = 0$ by injectivity), and there are $n$ of them, so they span. Therefore they are a basis for $\mathbb{F}^n$.

Patrick Stevens
  • 36,135
1

if $A$ is singular, it means there exists at least vector $u$ for which $Au=0$. Then you take an $x$ such that $Ax=y$ and you can observe that for any scalar $c$, you have $A(x+cu) = Ax + cAu = Ax$. Here, you proved that if $A$ is singular, then $x\mapsto Ax$ is not injective.

Now, if $x\mapsto Ax$ is not injective, it means there is at least an $x$ and a $y$ such that $x\ne y$ for which $Ax = Ay$. So, it means $A(x-y)=0$ and $x-y\ne 0$. So $A$ is singular.

davcha
  • 1,745
  • How do you know that if the matrix is singular, there exists a vector $u$ such that $Au=0$? I think it follows from the fact that singular matrix has a zero eigenvalue, and I asked not to use it. – user5539357 Feb 25 '16 at 16:23
  • Because the determinant is zero, of because the null space is not equal to zero... – davcha Feb 25 '16 at 19:22
  • Oh, sorry, I think I get it. Actually there always exists $u$ such that $Au=0$, just take $u=0$. Then taking some other vector, $x$, gives $Ax=y$, where $y$ is either zero or not. If it's zero, we conclude it's not injective. If not, then $A(x+cu)=Ax$, again meaning it's not injective. Right? – user5539357 Feb 25 '16 at 20:16
  • Yes, that's it. Also, you don't want to use the fact that there is a zero eigenvalue, but everything is connected, so any explanation can be reformulated in terms of eigenvalues, here – davcha Feb 25 '16 at 20:39
  • No. If you take a full rank matrix, there is no other vector than zero in the null space – davcha Feb 25 '16 at 20:49
0

Suppose that $A$ is singular. Basically, $A\mathbf{0}=\mathbf{0}$. Thus $\mathbf{0}$ is a root of $A\mathbf{x}=\mathbf{0}$. Since $A$ is singular, there is $\mathbf{y}$ such that $A\mathbf{y}=\mathbf{0}$ and $\mathbf{y}\ne \mathbf{0}$. (See here.)

Now suppose $A$ is not injective. then there is $\mathbf{x}$ and $\mathbf{y}$ such that $A\mathbf{x}=A\mathbf{y}$ and $\mathbf{x}\ne \mathbf{y}$. If $A$ is not singular, then there exists $A^{-1}$. Thus $$ \mathbf{x}=I\mathbf{x}=(A^{-1}A)\mathbf{x}=A^{-1}(A\mathbf{x})=A^{-1}(A\mathbf{y})=(A^{-1}A)\mathbf{y}=I\mathbf{y}=\mathbf{y}, $$ which is a contradiction.

choco_addicted
  • 8,786
  • 8
  • 24
  • 53
  • "Since $A$ is singular, there is $\mathbf{y}$ such that $A\mathbf{y}=\mathbf{0}$ and $\mathbf{y}\ne \mathbf{0}$." is the question at issue. – Patrick Stevens Feb 25 '16 at 09:09
  • Is it really at issue? It can be obtained not using eigenvalue. – choco_addicted Feb 25 '16 at 09:18
  • Yes, it can be obtained without eigenvalues, and that is what the OP asked you to do :P – Patrick Stevens Feb 25 '16 at 09:26
  • Sorry for my poor English, but I don't know what you mean. Do you mean what I wrote is tautology, or does other meaning exist? And... :P emoticon is sticking out a tongue, and seems to imply not good purpose. – choco_addicted Feb 25 '16 at 09:57
  • :P is sticking out a tongue; I meant "if I were speaking this, I would be smiling wryly". What you wrote is not a tautology; the OP asked for an explanation of why, if $A$ is singular, there is $y$ such that $Ay = 0$ and $y \not = 0$. Therefore what you wrote is simply restating the question (or, more accurately, assuming the answer). – Patrick Stevens Feb 25 '16 at 11:05
  • I used "tautology" as an act such that someone repeats same words. But the property I used can be obtained learning systems of linear equations, not assuming an answer. I'll clarify my post, but would you apologize for being sarcastic using an emoticon? – choco_addicted Feb 25 '16 at 11:28
  • If you like. I apologise for being sarcastic. However, I still think you haven't answered the question: you are claiming that $Ax = 0$ has infinitely many roots without justifying the claim. – Patrick Stevens Feb 25 '16 at 12:56
0

If $x \rightarrow Ax$ is not injective, then there exist two distinct values $x_1$, $x_2$ such that $A x_1 = A x_2$. If $A$ was not singular, then $A^{-1}A x_1 = A^{-1}A x_2$ i.e. $x_1 = x_2$.

This proves by contradiction that if $x\rightarrow A x$ is not injective, $A$ is singular.

I am still looking at the other direction.

Urukann
  • 238
0

We can also make everything a little more general. In particular:

Proposition 0. Let $K$ denote a field.

Then for all finite-dimensional $K$-modules $Y$ and $X$ satisfying $Y\stackrel{\mathrm{dim}}{=}X$ , every morphism $f:Y\leftarrow X$ that is at least one of {injective, surjective} is an isomorphism.

Proof sketch. Suppose $f$ is injective. Then we know that $f(X)\stackrel{\mathrm{dim}}{=}X$. Hence $f(X)\stackrel{\mathrm{dim}}{=}Y$ Since $Y$ is finite-dimensional, this implies that $f(X)=Y$. In other words, $f$ is surjective. Hence $f$ is an isomorphism.

Suppose $f$ is surjective. Then we can realize $f$ as a square matrix by choosing a basis for $Y$ and another basis for $X$. This matrix will be full-rank; and, hence, by the invertible matrix theorem, invertible. So $f$ is an isomorphism.

By the way, the theorem under question could reasonably be called the "Pigeonhole principle for linear transforms between finite-dimensional vector spaces" or some variant on that.

goblin GONE
  • 67,744