Determining the general perpendicular normal Given a vector $n \in \mathbb R^3$, how can I find (any) perpendicular normal $x$, such that $n^T\cdot x=0$ for all possible values of $n$ (i.e. with no edge cases)
 A: I’m not sure what you mean by “no edge cases” here. Most methods require at least some case analysis to avoid a degenerate case. Bob Werner’s answer does give a nifty case-free algorithm that looks like it will generalize to higher-dimensional spaces, but it seems like overkill for the problem in $\mathbb R^3$.  
Given a vector $n=(a,b,c)\in\mathbb R^3$, its cross products with the standard basis vectors $$n\times(1,0,0) = (0,c,-b) \\ n\times(0,1,0) = (-c,0,a) \\ n\times(0,0,1) = (b,-a,0)$$ are all orthogonal to $n$. If $n$ is nonzero, then at least two of these are nonzero. If you want all of the orthogonal vectors to $n$, choose two of the above vectors that are linearly independent: their span is the set of vectors orthogonal to $n$, but this is simply the plane through the origin with $n$ as a normal.
A: Levent Kitis posted a solution on UseNet sci.math.  The first component of the vector is altered with the vector's norm, then a symmetric orthogonal Householder matrix is formed using the altered vector.  The first row of the Householder matrix parallels the original vector, and the other two rows are perpendicular to it:
Let the given normal vector $b$ have components $b_1, b_2, b_3$
$b = (b_1, b_2, b_3)$
and let $B$ denote the magnitude of $b$.
Here is an algorithm that finds two unit vectors perpendicular to
$b$ and perpendicular to each other:
(1) Let $v = (b_1 + B, b_2, b_3)$ or $v = (b_1 - B, b_2, b_3)$ whichever makes
the first component bigger in absolute value.
(2) Form the three by three matrix $H$
$H = I - 2 v v^T/(v^T v)$
where $I$ is the identity matrix and $T$ denotes the transpose.
The first row of $H$ is a unit vector parallel to $b$.
The other two rows are unit vectors perpendicular to $b$
and perpendicular to each other.
Explicitly, with $V$ set equal to the square of the magnitude of $v$
$V = v_1^2 + v_2^2 + v_3^2$
the first row of $H$ is
$[ 1 - 2 v_1^2/V,\; -2 v_1 v_2/V,\; -2 v_1 v_3/V ]$
The second row is
$[ -2 v_1 v_2/V,\; 1 - 2 v_2^2 /V,\; -2 v_2 v_3/V ]$
and the third row
$[ -2 v_1 v_3/V,\; -2 v_2 v_3/V,\; 1 - 2 v_3^2/V ]$
A: 1st method : Working with coordinates, let $n=(a,b,c)^T$. One at least of its coordinates is non zero (otherwise it would be the null vector). 
Let us assume it is $a \neq 0$.
Let the generic vector orthogonal to $n$ be $u=(x,y,z)^T$ with $$ax+by+cz=0,$$ 
meaning that $x=-(b/a)y-(c/a)z$. Thus the general orthogonal vector has parametric representation :
$$\begin{pmatrix}x\\y\\z\end{pmatrix}
=\begin{pmatrix}-(b/a)y-(c/a)z\\y\\z\end{pmatrix}
=y \begin{pmatrix}-b/a\\1\\0\end{pmatrix}+ z \begin{pmatrix}-c/a\\0\\1\end{pmatrix}$$
for any real $y,z$, generating evidently a 2-dimensional space.

2nd method : if you are looking for a "closed form" formula, valid for any $n$, without distinguishing cases, here is one. Consider the skew-symmetric matrix :
$$X_n:=\left(\begin{array}{rrr}0&-c&b\\c&0&-a\\-b&a&0\end{array}\right) \ \ \ \ \text{with} \ n=(a,b,c)^T\tag{1}$$
then, the normal plane to $n$ is the range space $Range(X_n)$.
Why that ? Because $X_n$ is the matrix naturally associated with the cross product with vector $n$, as proven by the following computation :
$$\text{for} \ v:=(x,y,z)^T, \ \ X_n v=\left(\begin{array}{rrr}0&-c&b\\c&0&-a\\-b&a&0\end{array}\right)\left(\begin{array}{r}x\\y\\z\end{array}\right)=\underbrace{\left(\begin{array}{r}bz-cy\\cx-az\\ay-bx\end{array}\right)}_{n \ \times \ v}$$
Remark : operator $X_{n}$ is classical. See for example http://www.blackmesapress.com/CrossProduct.htm.
A: From vector $n$, find the largest component, in absolute value. If the others are not zero, set it to $0$, to get $n'$. Otherwise also set one of the other components to $1$. Then orthogonalize $$x=n'-\frac{(n\cdot n')}{|n|^2}n$$
