Degrees of Freedom of a Unitary Matrix Proof

My book states that a 3$\times$3 unitary matrix has 9 degrees of freedom, but I have trouble seeing why that is true. So I want to try and show that an $n\times n$ matrix has $n^2$ degrees of freedom.

Base case $n=1$: This is just a matrix with one entry which has length 1. It is clear that any entry with length 1 will do. So I have $1 = 1^2$ degree of freedom

$n \implies n+1$: Suppose we have an $n \times n$ unitary matrix and it has $n^2$ degrees of freedom. I want to now show that a $(n+1) \times (n+1)$ unitary matrix has $(n+1)^2$ degrees of freedom. If I add a $(n+1)$th row and column to the $n \times n$ unitary matrix, I have added $(n+1) + n = 2n + 1$ entries. For every entry $a_{ij}$ I have added, I need to ensure that each $a_{ij}^2 = 0$ in order for the matrix to be unitary. Since there are numerous ways to choose $a_{ij}$ such that $a_{ij}^2$ = 0, I have added $2n+1$ degrees of freedom. So the total degrees of freedom is $n^2 + 2n + 1 = (n+1)^2$.

Can I get some feedback on this proof? Thanks in advance!

Note It seems like my approach above is at a dead end.

-
I realize that I have an error when picking the entries $a_{ij}$ for there to be a unitary matrix. Is there an easy fix? – Student Nov 19 '12 at 18:49
I don't see a way to fix this. The plan seems flawed: you cannot start with a given $n\times n$ unitary matrix and add something to get an $(n+1)\times(n+1)$ matrix. Most of the $(n+1)\times(n+1)$ unitary matrices don't have an $n\times n$ unitary submatrix. – Dan Shved Nov 19 '12 at 18:51
Induction is not really a natural approach to this problem in my opinion. Your $n-1 \times n-1$ submatrix is generally not unitary (because you cannot add a non-zero entry to a unit length vector and have it remain unit length). A more fundamental problem is: What exactly do you mean by "degrees of freedom"? It is not dimension because the unitary matrices do not form a subspace. So what exactly is it are you trying to prove? – EuYu Nov 19 '12 at 18:53
It would be good to know what exactly you mean by degrees of freedom. How strictly is this notion defined in the book? If I had to formulate the question rigorously, I'd have to use the notion of a manifold. Does your book do that or does it formulate things less rigorously? – Dan Shved Nov 19 '12 at 18:53
Here is a hand waving viewpoint: The unitary matrix is characterized by the constraints $u_i^* u_j = \delta_{ij}$ for $i\geq j$, where $u_i$ are the columns of $U$. The constraints $u_i^* u_i = 1$ form 3 'real' constraints and the others form 3 'complex' constraints. Hence in terms of a real parameterization, there are 18 real parameters for a 3x3 matrix, with 3 real constraints and three complex constraints. Since you can view a complex constraint as two real ones, this corresponds to a remaining $18-3-2\cdot 3 = 9$ real parameters (loud sounds of hand waving in background). – copper.hat Nov 19 '12 at 19:18

copper.hat has already given an answer in the comments. This is the best answer I can think of. But there are also alternative "pieces of evidence" in support of $n^2$ degrees of freedom. Maybe they will be useful too.
We know that the identity matrix $I$ is unitary. Let us look at unitary matrices that are really close to $I$, i.e. at matrices $A=I+\Delta$, where all the elements of $\Delta$ are very small. Since $A$ is unitary, we have $$I = A^H A = (I+\Delta)^H (I + \Delta) = I + \Delta + \Delta^H + \Delta^H \Delta,$$ and so $$0 = \Delta + \Delta^H + \Delta^H \Delta \approx \Delta + \Delta^H.$$ In the last approximate equality I used the fact that elements in $\Delta^H \Delta$ are way smaller than elements in $\Delta$ and $\Delta^H$. So, $\Delta$ is approximately skew-Hermitian. And it is quite easy to see that skew-Hermitian matrices have $n^2$ degrees of freedom, because you can choose any complex numbers above the main diagonal (this gives you $2\cdot\frac{n^2-n}{2}$ degrees of freedom) and you can choose any imaginary numbers on the main diagonal (this is $n$ more degrees of freedom). This isn't rigorous, especially in that part when we use the word "approximate". But we saw that there is some sort of a connection between unitary and skew-Hermitian matrices.
This connection is deeper than it seems at first sight. For instance, it can also be demonstrated using the matrix exponential. It turns out that if matrix $X$ is skew-Hermitian, then $e^X$ is unitary. Even more, any unitary matrix is in fact a matrix exponential of some skew-Hermitian matrix. So it's no big surprise that their numbers of degrees of freedom are the same.
Finally, if you'd like to find out how all this stuff can be formulated rigorously, then differential geometry can give you the answers. One of the central notions in differential geometry is that of a smooth manifold. copper.hat's comment can be turned into a rigorous proof of the fact that $U(n)$, the set of all unitary $n \times n$ matrices, is an $n^2$-dimensional submanifold of the Euclidean space $\mathbb{R}^{2n^2}$.