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.
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$.