Algorithm for finding orthogonal complement in inner product spaces Is there a general procedure for calculating a basis for the orthogonal complement of a given subspace (with a given basis)? For $\mathbb R^n$ this amounts to finding the nullspace of a matrix with the basis vectors for rows, but this is just because of the definition of the standard inner product.
What about the general case?
 A: Find a basis for the subspace. Extend to a basis of the whole vector space. Orthogonalize the entire basis using Gram-Schmidt, with the basis of the subspace first; this will give you an orthogonal basis of the subspace, and the remaining vectors will form a basis for the orthogonal complement.
A: Take a closer look at what you’re doing when you use the algorithm that you describe for computing an orthogonal complement relative to the Euclidean scalar product $\langle\cdot,\cdot\rangle$: you’re solving the homogeneous system of linear equations $$\begin{align}
\langle\mathbf w_0,\mathbf x\rangle &= 0 \\
\langle\mathbf w_1,\mathbf x\rangle &= 0 \\
\vdots \\
\langle\mathbf w_m,\mathbf x\rangle &= 0 \\
\end{align}$$ where the $\mathbf w_k$ are a basis for the subspace. This can be written as the single equation $W^T\mathbf x=0$, where $W$ is the matrix with these basis vectors as its columns. Solving this amounts to finding the nullspace of $W^T$, as you said.  
For an arbitrary inner product $(\cdot,\cdot)$ over $\mathbb R^n$, you can set up a similar system of linear equations and solve it to find the orthogonal complement relative to that inner product. To express this system in matrix form, we take advantage of the fact that any inner product over $\mathbb R^n$ can be expressed in terms of the Euclidean scalar product as $(\mathbf u,\mathbf v)=\langle\mathbf u,A\mathbf v\rangle$, where $A$ is a fixed symmetric positive-definite matrix. This matrix is given by $A_{ij}=(\mathbf e_i,\mathbf e_j)$, where the $\mathbf e_k$ are the standard basis vectors. With this matrix in hand, the system of equations can be written $W^TA\mathbf x=0$, so finding the orthogonal complement of the subspace is a matter of computing the nullspace of $W^TA$.   
The process for $\mathbb C^n$ is similar, except that the inner product matrix will be Hermitian and you need to use conjugate transposes.
A: If the subspace with known basis is of dimension $k$ and the full space is $\mathbb{R}^n$, take a set of  $n-k$ random vectors $v_k$. Subtract the projection onto the basis for each random vector $v_k$ and each basis vector $i$, $$v_k = v_k - P_i(v_k)$$Now you will have a basis for the complementary subspace: $\{v_1,\cdots,v_{n-k}\}$.
Construct your projection like so:
$$P = SDS^{\dagger}$$ with $D$ diagonal and $D_{jj} = \delta_{(j\leq k)}$, and the first $k$ columns of $S$ be basis vectors and the rest zeros, $S^\dagger$ denotes pseudo-inverse.
Furthermore stuff $v_k$ as columns into $V$. Now just do $(I-P)V$ and you will have a basis of the complementary space as the columns of this product.
