For example, Ax=b is an overdetermined linear equations. We want to minimize $||Ax-b||_2$. So the solution is $x = (A^TA)^{-1}A^Tb$.
What I want to ask is how does the norm of x , $||x||_2$, change with the increase of the number of coefficients? Say, the size of A changes from $n\times1$ to $n\times n$.
It seems like it has something to do with what A is and $||x||_{2}$ seems to increase. If we assume elements in A are from standard normal distribution. How to prove $||x||_{2}$ increases? Can someone give me an idea?
It sounds like the problem you want to solve is: Given an $m\times n$ matrix $A$ and a vector $\vec{b}\in\Bbb R^m$, what vector $\widehat{x}$ minimizes $\lVert A\widehat{x}-\vec{b}\rVert$?
The first important thing to note is that $\lVert A\widehat{x}-\vec{b}\rVert$ is minimized when $A\widehat{x}=P\vec{b}$ where $P\vec{b}$ is the projection of $\vec{b}$ onto $\operatorname{Col}(A)$.
Now, we are tasked with the problem of finding $\widehat{x}$ solving $A\widehat{x}=P\vec{b}$. If $A$ has full column rank, then your mentioned formula $\widehat{x}=(A^\top A)^{-1}A^\top\vec{b}$ works. However, if $A$ does not have full column rank, then $(A^\top A)$ is not invertible, so this formula will not work.
However, it turns out that we can solve $A\widehat{x}=P\vec{b}$ regardless of whether or not $A$ has full column rank. One way to do this is to use the Moore-Penrose inverse $A^+$ of $A$. Given $A^+$, we may define $\widehat{x}=A^+\vec{b}$.
Computing $A^+$ in general is a difficult problem. A classical way of computing $A^+$ is to use the singular value decomposition of $A$. The wikipedia entry for Moore-Penrose inverses lists several other constructions as well.