# Is there an algorithm that produces a basis for $A^\perp$ given a basis for $A$?

Let $A \subseteq \mathbb{R}^k$ denote a linear subspace with basis $\{b_0,\ldots,b_{n-1}\}.$ Suppose we wish to find a basis for the orthogonal complement $A^\perp$ with respect to the usual dot product. Is there an algorithm for doing this, that can realistically be done by hand? (For sufficiently small $n$ and $k$, of course, e.g. $n=2,k=4$). I do not demand that the basis we construct for $A^\perp$ be orthonormal or even orthogonal, since we can just run Gram-Schmidt at the end if we really want this.

• If you were in a general inner product space other than $\mathbb{R}^k$ you wouldn't be able to make a meaningful algorithm, since $A$ and $A^{\perp}$ are separate direct summands, and so are essentially independent. Nov 11, 2014 at 7:18

## 2 Answers

The idea is to take a basis of $A$, complete in any way you want to a basis of the whole space, and then do Gram-Schmidt to get an orthogonal basis out of it. The elements produced out of the elements of the basis of $A$ will stay in $A$ and now be orthogonal. The elements of the basis that were out of $A$ are still out of $A$ but now orthogonal to $A$. They, the latter subset, will be an orthogonal basis of $A^{\bot}$.

Consider the system of equations $\langle b_i,x\rangle=0,\;i=0,\ldots,n-1$. Obviously, every $x\in\mathbb{R}^k$ is in the orthogonal complement if and only if it solves the above system. So your question reduces to solving a homogeneous system of linear equations.