Pseudo-Orthogonal Matrices
TODO: Add more interesting things about Pseudo-Orthogonal matrices, i.e., Nick Higham's blog post, etc.
Prof. Vandenberghe has a great set of additional exercies where I ran across the idea of an pseudo-orthogonal matrix, defined as follows. He first defines a signature matrix, a square matrix with diagonal elements are either \(+1\) or \(-1\). Then if \(S\) is a signature matrix, and \(A\) is a square matrix that satisfies:
$$
A^TSA = S
$$
then we say that \(A\) is pseudo-orthogonal with respect to \(S\). The exercise I'm referencing is exercise 6.11.
(a)
To show that
$$
A = S - \frac{2}{u^TSu} uu^T
$$
is pseudo-orthogonal, we have the following:
$$
\begin{aligned}
A^TSA &= \left(S - \frac{2}{u^TSu}uu^T \right)^T S \left(S - \frac{2}{u^TSu}uu^T\right) \\
&= \left(S^T - \frac{2}{u^TSu}uu^T \right) S \left(S - \frac{2}{u^TSu}uu^T \right) \ \text{(distributing transpose)} \\
&= \left(I - \frac{2}{u^TSu} uu^TS\right)\left(S - \frac{2}{u^TSu}uu^T\right) \ \text{(note: \(SS = I\))} \\
&= S - \frac{2}{u^TSu} uu^T - \frac{2}{u^T S u} S uu^T S + \frac{4}{(u^TSu)^2} u(u^TSu)u^T \ \text{(distributing)} \\
&= S - \frac{4}{u^TSu} uu^T + \frac{4}{u^TSu} uu^T \text{(since \(S\) is diagonal, can be moved anywhere as an operation)} \\
&= S
\end{aligned}
$$
as desired.
(b)
To show that \(A\) is invertible, first note that since \(S\) is a diagonal matrix, then it has an inverse: itself \(SS = I\). Then, we have the following:
$$
\begin{aligned}
S &= A^TSA \\
SS &= SA^TSA \\
I &= SS A^TA \\
I &= A^TA
\end{aligned}
$$
so \(A\) has an inverse: \(A^T\).
(c)
If \(A\) is psuedo-orthogonal, then we can then have the following setup:
$$\begin{aligned}
Ax &= b \\
A^TSAx &= A^TSb \\
Sx &= A^TSb \\
SSx &= SA^TSb \\
x &= SSA^Tb \\
x &= A^Tb
\end{aligned}
$$
the matrix-vector multiplication \(A^Tb\) costs \(O(n^2)\) FLOPs, and that is the only multiplication we need to do.
(d)
If \(A\) is is pseudo-orthogonal, then we have the following:
$$\begin{aligned}
A^TSA &= S \\
ASA^TSA &= A \ \text{(\(SS = I\))} \\
ASA^TSAA^{-1} &= AA^{-1} \\
ASA^TS &= I \\
ASA^TSS &= S \\
ASA^T &= S
\end{aligned}
$$
as desired.