How does one figure out the orthonormal basis from just the inner product without brute force for an inner product space? Lets say $(V, \left < \right> )$ is an inner product space. How does one obtain an orthonormal basis $(e_i)$ from just the inner product by directly calculating?
By that I mean if $x \in V$, then to obtain say an orthogonal basis, we find $y$ such that $(x,y) =0$. To get norm $1$, we reinforce that $(y,y) = 1$.
Let's actually put this into context with an example. I will adapt this from this link from physics with some slight changes.
Consider the skew-Hermitian matrix group from Linear Algebra with $0$ trace $B = \{ A \in M_{n\times n}(\mathbb{C}) : A = -A^* \}$ with the inner product $(A_i, A_j) = -\frac{1}{2}tr(A_iA_j)$ (I added $1/2$ that we obtain orthonormal matrices). It can be shown that an orthonormal basis contains the Gell-Mann matrices.
Now one can obtain those Gall-Mann by just deducing the skew-Hermitian property without writing down all the diffuclt procedures I wrote in the beginning - writing a generic element $x \in V$ and figuring out what the formulas are for $y$ so that $(x,y) = 0$ and $(y,y) =1$. But this seems like it's only possible if we know what space we are working on. How does one do this if we have no idea on the underlying space? I am imagine this gets more difficult if the group is more complicated. 
 A: You seem to have some confusion on how to get a starting basis to even orthogonalize. I'll show the method I use in the case $n=2$. 
The space $B$ will be a subpace of $M_{2\times2}(\mathbb{C})$. Take some generic matrix $A$ and set up the equation for a skew Hermitian matrix. 
$$ A^\dagger + A = 0 $$ 
$$ \left(\begin{array} \ a & b \\ c & d \end{array}\right)^\dagger+
\left(\begin{array} \ a & b \\ c & d \end{array}\right)=0
$$
$$ \left(\begin{array} \ \bar{a} & \bar{c} \\ \bar{b} & \bar{d} \end{array}\right)+
\left(\begin{array} \ a & b \\ c & d \end{array}\right)=0
$$
$$ \left(\begin{array} \ \bar{a} + a & \bar{c} + b \\ \bar{b}+c & \bar{d}+d \end{array}\right)=0
$$
From this we get three independent equations. 
$$\Re(a)=0$$
$$\Re(d)=0$$
$$b=-\bar{c}$$
add to this the equation which comes from the requirement that the trace be zero. 
$$ a+d=0$$
So the matrix has the general form, 
$$ \left( \begin{array} \ ix & y+iz \\ -(y-iz) & -ix \end{array}\right)$$
where now $x,y,z,w$ are all real. 
$$ \left( \begin{array} \ xi & y+iz \\ -(y-iz) & -ix \end{array}\right) = 
 x \left( \begin{array} \ i & 0 \\ 0 & -i \end{array}\right)
 + y \left( \begin{array} \ 0 & 1 \\ -1 & 0 \end{array}\right)  
 + z \left( \begin{array} \ 0 & i \\ i & 0 \end{array}\right)  
$$
Clearly the four matrices multiply $x,y,$ and $z$ respectively form a basis for the space $B$. 
This method can be used to get a basis for $B$ for any given $n$. Once you have this basis you can then orthogonalize it using Graham Schmidt as indicated by the other answer. 
If you try my method for general $n$ using index notation you may be able to derive the more general result. 

Notice that the result ended up just being $i$ times the Pauli matrices. These are in fact orthogonal with respect to your inner product. If you look at the 3x3 Gell-Mann matrices you will see the same structure of the Pauli matrices in them. This may lead to a clever way of deducing the orthogonal basis. 
A: There is no canonical choice of orthonormal basis for an inner product space, just as there is no canonical choice of basis for a vector space. One doesn't just spring forth from the situation or arise naturally in any way.
Of course you can take a basis and create an orthonormal basis from it using the Gram-Schmidt process, but I assume you would consider that brute force.
