# Simple solution to linear system, is this a two sided implication?

Consider the system $Ax=y$ where $A \in Mat_{n\times n}(\mathbb R)$, and $x,y \in \mathbb R^n$.

Suppose that $A,y$ are known to us, and we want to find $x$.

It is clear to see that if $rank(A)=n$ then we have no problem and we can easily find $x$.

My question is, does it work the other way around? suppose we don't know the rank of $A$, but a wizard comes and says "Don't worry, I guarantee you that for any $y$ of your choice, we can find $x$.", can we infer that $rank(A)=n$?

• Well, if the range of $A$ is the entire space $\mathbb{R}^n$, what is $\operatorname{rank}(A)$? – Zoran Loncarevic Sep 29 '15 at 20:16
• it is $n$. Didn't think of the range. Silly me. – Oria Gruber Sep 29 '15 at 20:17

Yes. If $\forall y \in \mathbb{R}^n$, $\exists x$ such that $Ax=y$, then rank $A = n$.

Given $A$, we have the matrix equation

$$Ax=y$$

and, as you have indicated, that for all y, there exists an $x$ such that the equation is satisfied, this indicates that rank $A = n$. The reason for this is that the columnspace of $A$ must be equal to all of $\mathbb{R}^n$. If this were not the case, then we would be able to find a $y \in \mathbb{R}^n$ such that $Ax=y$ was had no solution $x$. Since rank $A$ is the dimension of the columnspace of $A$, we have that rank $A = n$.

• Thank you for your contribution. I also wrote an answer. Would appreciate fact-check :) – Oria Gruber Sep 29 '15 at 20:17

Just realized. Suppose $rank(A)<n$, then $0$ is an eigenvalue of $A$. Choose $y$ to be the zero vector. We have no way of knowing if $x=0$ or $x\neq 0$ but it is the eigenvector that corresponds to eigenvalue $0$ of $A$.

Meaning, if $rank(A) <n$, we can't always determine $x$ from $y$. And conversely, if we can always determine $x$ from $y$, then $rank(A)=n$.