The set of vectors should also span the whole space.
If we know the dimension of the space then we should simply count the orthonormal vectors and make sure that we have as many vectors in our basis as the dimension of the space.
Otherwise, we have to prove that every vector is a linear combination of the basis vectors.
Basically, you’re going to perform a partial diagonalization of $M$.
Let $\{v_2,\dots,v_n\}$ be a basis for the orthogonal complement of $v_1$ and assemble $v_1$ and the other basis vectors into the matrix $B$. Then $$B^{-1}MB = \begin{bmatrix}\lambda_1 & \mathbf 0^T \\ \mathbf 0 & M'\end{bmatrix}.$$ The submatrix $M'$ is the “reduced” matrix that you’re looking for. Its eigenvalues are the remaining eigenvalues of $M$, but keep in mind that you’re no longer working in the standard basis, so once you’ve found the coordinates of its eigenvectors, you’ll need to convert back into the original basis.
As for what to choose as the basis for $v_1^\perp$, I’m not sure that an orthonormal basis is the best practical choice. Because of all the normalization the entries of $M'$ are unlikely to be “nice,” which will just make it more likely that you’ll make errors if you’re doing this by hand. An orthogonal basis might be convenient because it makes the inversion for the change of basis easier: $B^{-1}MB = \frac1{\det B}B^TMB$, but you have to trade that off against the work required to produce this basis. A basis that’s very simple to generate is $\{(2,-1,0,0,\dots)^T, (3,0,-1,0,\dots)^T, (4,0,0,-1,\dots)^T, \dots\}$ and inverting the resulting matrix doesn’t seem like it would be too bad. You could, for instance, perform Gaussian elimination on $[B\mid MB]$ to compute $B^{-1}MB$.
Using your basis, we compute $$B^{-1}MB = \begin{bmatrix}60&0&0&0\\0&-16&28&-32\\0&-84&-168&102\\0&92&4&-86\end{bmatrix}.$$ The upper-left element is indeed the eigenvalue associated with $(1,2,3,4)^T$ and the rest of that row and column consists of zeros, as expected.
Best Answer
If $x = \sum_i a_i v_i$ where $\{v_i\}$ form an orthonormal basis, $||x|| = \sqrt{\sum_i |a_i|^2}$. This is just Pythagorean theorem.