Matrix norm inequality : $\| Ax\| \leq |\lambda| \|x\|$, proof verification 
Suppose that $A$ is a normal $n\times n$ matrix.  Show that $\|Ax \| \geq |\lambda_n|\|x\|$ for all 
  $x \in \mathbf{C}^n$, if $\lambda_n$ is the eigenvalue to $A$ of smallest absolute value. Is this also always true when $A$
  is not normal?  Give a proof
  or a counterexample!

First question, does this depend on which norm I choose? Since $x\in\mathbf{C}^n$, then I am inclined to choose the induced norm (whatever its real name is), but I do not know where $A$ exists. If I can choose the 'natural one', then
$$ \|Ax\|^2 = (Ax,Ax) = x^*A^*Ax.$$
Since $A$ is normal, it is unitarily similar to diagonal matrix $\Lambda$, so if $y = Ux$ (isometry) one gets
$$ x^*A^*Ax = x^*U^*\Lambda^*\Lambda U x = y^*\Lambda^*\Lambda y = 
\sum_i^n |\lambda_i|^2 |y_i|^2 \geq |\lambda_n|^2 \|y\|^2$$
and because $\|y\| = \|x\|$ one gets $\|Ax\| \geq |\lambda_n|\|x\|$. Is this correct?
Suppose $A$ not normal, then one can obtain the SVD $A = W\Sigma V^*$ and apply a similar proof
$$ \|Ax\|^2 = \dots = x^*V\Sigma^* \Sigma V^* x.
$$
Take $v = V^*x$, isometric, and singular values $\sigma_1 \geq \dots \geq \sigma_n \geq 0$, one gets
$$ x^*V\Sigma^*\Sigma V^*x = v^*\Sigma^*\Sigma v = \sum_i^n \sigma_i^2 |v_i|^2
\geq \sigma_n^2 \|v\|^2
$$
so, $\|v\| = \|x\|$ one gets $\|Ax\| \geq \sigma_n\|x\|$. And since 
$\sigma_n = \sqrt{\lambda_n} \geq \lambda_n$ for $\lambda_n \leq 1$, the statement is probably not always true, thus I can find a counterexample.
I still feel like the not-normal case should be true, since it is on verge of being true, and because of my insecurity with norms and singular values. Any improvements, criticism and hints are appreciated.
 A: Normally we talk about normal matrices in a space with inner product, and we consider the norm induced by the inner product (unless explicitly said that another norm should be considered). So I will assume we are supposed to use the norm induced by the inner product.


*

*Your proof for the case where $A$ is normal is correct.

*The result is not valid is $A$ is not normal. Here is a simple counter-example. 
Let $A$ be the matrice over $\mathbb{C}^2$ defined as  $$ A =\left( \begin{array}{cc}
1 & 1 \\
0 & 1 \end{array} \right) $$ It is easy to see that $$ A^* =\left( \begin{array}{cc}
1 & 0 \\
1 & 1 \end{array} \right) $$ and that $$ AA^*= \left( \begin{array}{cc}
2 & 1 \\
1 & 1 \end{array} \right) \neq \left( \begin{array}{cc}
1 & 1 \\
1 & 2 \end{array} \right) = A^*A$$ So $A$ is not normal. The eingenvalue of A of smallest absolute value is $1$ (in fact, it is the only eingenvalue). Take $x=(-1,1)$, then $$\|Ax\|=\|(0,1)\| = 1 < 1.\|x\| =\sqrt{2}$$
Remark: In your argument for the non-normal case, you wrote $\sigma_n = \sqrt{\lambda_n}$. It is not true. The non-zero singular values of $A$ are the square root of non-zero eingenvalues of $AA^*$ (or $A^*A$). 
If $A$ is normal, the eingenvalues of $AA^*$ are the square of the modules of the the eingenvalues of $A$, and so the non-zero singular values of $A$ are precisely the modules of non-zero eingenvalues of $A$  
However, if $A$ is NOT normal, the singular values of $A$ may be very different from the modules of eingenvalues of $A$.      
