Checking positive semi-definiteness of integer matrix
You can tridiagonalize an integer matrix into an integer tridiagonal matrix using Householder reflections times integers. The resulting tridiagonal matrix will be SPD iff the original is. Sylvester’s criterion can be checked in linear time for tridiagonal matrices, since the determinants follow a recurrence relation:
If we are checking for positive definiteness, Sylvester's criterion can be evaluated in linear time via the recurrence since we only need to check $n$ principle minors. For positive semidefiniteness, we must additionally check all $O(n^2)$ minors given by intervals of rows/columns. This takes $O(n^2)$ time, which is still less than the tridiagonalization step.
- Tridiagonalization: https://math.byu.edu/~schow/resources/householder.pdf
- Recurrence: https://en.m.wikipedia.org/wiki/Tridiagonal_matrix
For small symmetric matrices, you could look at the characteristic polynomial. The real symmetric matrix $A$ is positive semidefinite iff the coefficients of the characteristic polynomial are alternating in sign. For $n \times n$ matrices this gives you $n$ integer expressions to check.
I wrote a program that takes a square integer matrix $H$ and produces square rational $P$ such that $P^T H P = D$ is diagonal and rational. In case it matters, $\det P = \pm 1.$ The program outputs in Latex. By Sylvester's Law of Inertia, $H$ is positive definite if and only if $D$ is positive definite, and there is no approximation involved. It is really just repeated completing the square made up into a reverse direction algorithm by parties unknown. The algorithm is given in detail at http://math.stackexchange.com/questions/1388421/reference-for-linear-algebra-books-that-teach-reverse-hermite-method-for-symmetr The way I like to write this, we introduce one new "elementary" matrix at a time and keep track of various things. In the most fortunate outcome, only one type of matrix is used and $P$ is upper triangular, but this does not always happen.
Oh, this works fine with semi-definite matrices. If the diagonal $D$ has some positive entries and some (diagonal) zero entries, then $H$ is positive semi-definite. No guesswork.
Here is the input
~jagy@phobeusjunior:~$ ./matrix_congruence 5
input row number 1 here 0 1 2 3 4
0 1 2 3 4
input row number 2 here 1 5 6 7 8
1 5 6 7 8
input row number 3 here 2 6 9 10 11
2 6 9 10 11
input row number 4 here 3 7 10 12 13
3 7 10 12 13
input row number 5 here 4 8 11 13 14
4 8 11 13 14
$$ P^T H P = D $$ $$\left( \begin{array}{rrrrr} 0 & 1 & 0 & 0 & 0 \\ 1 & - \frac{ 1 }{ 5 } & 0 & 0 & 0 \\ 4 & - 2 & 1 & 0 & 0 \\ \frac{ 8 }{ 5 } & \frac{ 1 }{ 5 } & - \frac{ 8 }{ 5 } & 1 & 0 \\ \frac{ 8 }{ 11 } & \frac{ 1 }{ 11 } & \frac{ 3 }{ 11 } & - \frac{ 17 }{ 11 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrrr} 0 & 1 & 2 & 3 & 4 \\ 1 & 5 & 6 & 7 & 8 \\ 2 & 6 & 9 & 10 & 11 \\ 3 & 7 & 10 & 12 & 13 \\ 4 & 8 & 11 & 13 & 14 \\ \end{array} \right) \left( \begin{array}{rrrrr} 0 & 1 & 4 & \frac{ 8 }{ 5 } & \frac{ 8 }{ 11 } \\ 1 & - \frac{ 1 }{ 5 } & - 2 & \frac{ 1 }{ 5 } & \frac{ 1 }{ 11 } \\ 0 & 0 & 1 & - \frac{ 8 }{ 5 } & \frac{ 3 }{ 11 } \\ 0 & 0 & 0 & 1 & - \frac{ 17 }{ 11 } \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrr} 5 & 0 & 0 & 0 & 0 \\ 0 & - \frac{ 1 }{ 5 } & 0 & 0 & 0 \\ 0 & 0 & 5 & 0 & 0 \\ 0 & 0 & 0 & \frac{ 11 }{ 5 } & 0 \\ 0 & 0 & 0 & 0 & \frac{ 6 }{ 11 } \\ \end{array} \right) $$
$$ D_0 = H $$ $$ E_j^T D_{j-1} E_j = D_j $$ $$ P_{j-1} E_j = P_j $$ $$ E_j^{-1} Q_{j-1} = Q_j $$ $$ P_j Q_j = I $$ $$ P_j^T H P_j = D_j $$ $$ Q_j^T D_j Q_j = H $$
$$ H = \left( \begin{array}{rrrrr} 0 & 1 & 2 & 3 & 4 \\ 1 & 5 & 6 & 7 & 8 \\ 2 & 6 & 9 & 10 & 11 \\ 3 & 7 & 10 & 12 & 13 \\ 4 & 8 & 11 & 13 & 14 \\ \end{array} \right) $$
==============================================
$$ E_{1} = \left( \begin{array}{rrrrr} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) $$ $$ P_{1} = \left( \begin{array}{rrrrr} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{1} = \left( \begin{array}{rrrrr} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{1} = \left( \begin{array}{rrrrr} 5 & 1 & 6 & 7 & 8 \\ 1 & 0 & 2 & 3 & 4 \\ 6 & 2 & 9 & 10 & 11 \\ 7 & 3 & 10 & 12 & 13 \\ 8 & 4 & 11 & 13 & 14 \\ \end{array} \right) $$
==============================================
$$ E_{2} = \left( \begin{array}{rrrrr} 1 & - \frac{ 1 }{ 5 } & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) $$ $$ P_{2} = \left( \begin{array}{rrrrr} 0 & 1 & 0 & 0 & 0 \\ 1 & - \frac{ 1 }{ 5 } & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{2} = \left( \begin{array}{rrrrr} \frac{ 1 }{ 5 } & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{2} = \left( \begin{array}{rrrrr} 5 & 0 & 6 & 7 & 8 \\ 0 & - \frac{ 1 }{ 5 } & \frac{ 4 }{ 5 } & \frac{ 8 }{ 5 } & \frac{ 12 }{ 5 } \\ 6 & \frac{ 4 }{ 5 } & 9 & 10 & 11 \\ 7 & \frac{ 8 }{ 5 } & 10 & 12 & 13 \\ 8 & \frac{ 12 }{ 5 } & 11 & 13 & 14 \\ \end{array} \right) $$
==============================================
$$ E_{3} = \left( \begin{array}{rrrrr} 1 & 0 & - \frac{ 6 }{ 5 } & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) $$ $$ P_{3} = \left( \begin{array}{rrrrr} 0 & 1 & 0 & 0 & 0 \\ 1 & - \frac{ 1 }{ 5 } & - \frac{ 6 }{ 5 } & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{3} = \left( \begin{array}{rrrrr} \frac{ 1 }{ 5 } & 1 & \frac{ 6 }{ 5 } & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{3} = \left( \begin{array}{rrrrr} 5 & 0 & 0 & 7 & 8 \\ 0 & - \frac{ 1 }{ 5 } & \frac{ 4 }{ 5 } & \frac{ 8 }{ 5 } & \frac{ 12 }{ 5 } \\ 0 & \frac{ 4 }{ 5 } & \frac{ 9 }{ 5 } & \frac{ 8 }{ 5 } & \frac{ 7 }{ 5 } \\ 7 & \frac{ 8 }{ 5 } & \frac{ 8 }{ 5 } & 12 & 13 \\ 8 & \frac{ 12 }{ 5 } & \frac{ 7 }{ 5 } & 13 & 14 \\ \end{array} \right) $$
==============================================
$$ E_{4} = \left( \begin{array}{rrrrr} 1 & 0 & 0 & - \frac{ 7 }{ 5 } & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) $$ $$ P_{4} = \left( \begin{array}{rrrrr} 0 & 1 & 0 & 0 & 0 \\ 1 & - \frac{ 1 }{ 5 } & - \frac{ 6 }{ 5 } & - \frac{ 7 }{ 5 } & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{4} = \left( \begin{array}{rrrrr} \frac{ 1 }{ 5 } & 1 & \frac{ 6 }{ 5 } & \frac{ 7 }{ 5 } & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{4} = \left( \begin{array}{rrrrr} 5 & 0 & 0 & 0 & 8 \\ 0 & - \frac{ 1 }{ 5 } & \frac{ 4 }{ 5 } & \frac{ 8 }{ 5 } & \frac{ 12 }{ 5 } \\ 0 & \frac{ 4 }{ 5 } & \frac{ 9 }{ 5 } & \frac{ 8 }{ 5 } & \frac{ 7 }{ 5 } \\ 0 & \frac{ 8 }{ 5 } & \frac{ 8 }{ 5 } & \frac{ 11 }{ 5 } & \frac{ 9 }{ 5 } \\ 8 & \frac{ 12 }{ 5 } & \frac{ 7 }{ 5 } & \frac{ 9 }{ 5 } & 14 \\ \end{array} \right) $$
==============================================
$$ E_{5} = \left( \begin{array}{rrrrr} 1 & 0 & 0 & 0 & - \frac{ 8 }{ 5 } \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) $$ $$ P_{5} = \left( \begin{array}{rrrrr} 0 & 1 & 0 & 0 & 0 \\ 1 & - \frac{ 1 }{ 5 } & - \frac{ 6 }{ 5 } & - \frac{ 7 }{ 5 } & - \frac{ 8 }{ 5 } \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{5} = \left( \begin{array}{rrrrr} \frac{ 1 }{ 5 } & 1 & \frac{ 6 }{ 5 } & \frac{ 7 }{ 5 } & \frac{ 8 }{ 5 } \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{5} = \left( \begin{array}{rrrrr} 5 & 0 & 0 & 0 & 0 \\ 0 & - \frac{ 1 }{ 5 } & \frac{ 4 }{ 5 } & \frac{ 8 }{ 5 } & \frac{ 12 }{ 5 } \\ 0 & \frac{ 4 }{ 5 } & \frac{ 9 }{ 5 } & \frac{ 8 }{ 5 } & \frac{ 7 }{ 5 } \\ 0 & \frac{ 8 }{ 5 } & \frac{ 8 }{ 5 } & \frac{ 11 }{ 5 } & \frac{ 9 }{ 5 } \\ 0 & \frac{ 12 }{ 5 } & \frac{ 7 }{ 5 } & \frac{ 9 }{ 5 } & \frac{ 6 }{ 5 } \\ \end{array} \right) $$
==============================================
$$ E_{6} = \left( \begin{array}{rrrrr} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 4 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) $$ $$ P_{6} = \left( \begin{array}{rrrrr} 0 & 1 & 4 & 0 & 0 \\ 1 & - \frac{ 1 }{ 5 } & - 2 & - \frac{ 7 }{ 5 } & - \frac{ 8 }{ 5 } \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{6} = \left( \begin{array}{rrrrr} \frac{ 1 }{ 5 } & 1 & \frac{ 6 }{ 5 } & \frac{ 7 }{ 5 } & \frac{ 8 }{ 5 } \\ 1 & 0 & - 4 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{6} = \left( \begin{array}{rrrrr} 5 & 0 & 0 & 0 & 0 \\ 0 & - \frac{ 1 }{ 5 } & 0 & \frac{ 8 }{ 5 } & \frac{ 12 }{ 5 } \\ 0 & 0 & 5 & 8 & 11 \\ 0 & \frac{ 8 }{ 5 } & 8 & \frac{ 11 }{ 5 } & \frac{ 9 }{ 5 } \\ 0 & \frac{ 12 }{ 5 } & 11 & \frac{ 9 }{ 5 } & \frac{ 6 }{ 5 } \\ \end{array} \right) $$
==============================================
$$ E_{7} = \left( \begin{array}{rrrrr} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 8 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) $$ $$ P_{7} = \left( \begin{array}{rrrrr} 0 & 1 & 4 & 8 & 0 \\ 1 & - \frac{ 1 }{ 5 } & - 2 & - 3 & - \frac{ 8 }{ 5 } \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{7} = \left( \begin{array}{rrrrr} \frac{ 1 }{ 5 } & 1 & \frac{ 6 }{ 5 } & \frac{ 7 }{ 5 } & \frac{ 8 }{ 5 } \\ 1 & 0 & - 4 & - 8 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{7} = \left( \begin{array}{rrrrr} 5 & 0 & 0 & 0 & 0 \\ 0 & - \frac{ 1 }{ 5 } & 0 & 0 & \frac{ 12 }{ 5 } \\ 0 & 0 & 5 & 8 & 11 \\ 0 & 0 & 8 & 15 & 21 \\ 0 & \frac{ 12 }{ 5 } & 11 & 21 & \frac{ 6 }{ 5 } \\ \end{array} \right) $$
==============================================
$$ E_{8} = \left( \begin{array}{rrrrr} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 12 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) $$ $$ P_{8} = \left( \begin{array}{rrrrr} 0 & 1 & 4 & 8 & 12 \\ 1 & - \frac{ 1 }{ 5 } & - 2 & - 3 & - 4 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{8} = \left( \begin{array}{rrrrr} \frac{ 1 }{ 5 } & 1 & \frac{ 6 }{ 5 } & \frac{ 7 }{ 5 } & \frac{ 8 }{ 5 } \\ 1 & 0 & - 4 & - 8 & - 12 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{8} = \left( \begin{array}{rrrrr} 5 & 0 & 0 & 0 & 0 \\ 0 & - \frac{ 1 }{ 5 } & 0 & 0 & 0 \\ 0 & 0 & 5 & 8 & 11 \\ 0 & 0 & 8 & 15 & 21 \\ 0 & 0 & 11 & 21 & 30 \\ \end{array} \right) $$
==============================================
$$ E_{9} = \left( \begin{array}{rrrrr} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & - \frac{ 8 }{ 5 } & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) $$ $$ P_{9} = \left( \begin{array}{rrrrr} 0 & 1 & 4 & \frac{ 8 }{ 5 } & 12 \\ 1 & - \frac{ 1 }{ 5 } & - 2 & \frac{ 1 }{ 5 } & - 4 \\ 0 & 0 & 1 & - \frac{ 8 }{ 5 } & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{9} = \left( \begin{array}{rrrrr} \frac{ 1 }{ 5 } & 1 & \frac{ 6 }{ 5 } & \frac{ 7 }{ 5 } & \frac{ 8 }{ 5 } \\ 1 & 0 & - 4 & - 8 & - 12 \\ 0 & 0 & 1 & \frac{ 8 }{ 5 } & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{9} = \left( \begin{array}{rrrrr} 5 & 0 & 0 & 0 & 0 \\ 0 & - \frac{ 1 }{ 5 } & 0 & 0 & 0 \\ 0 & 0 & 5 & 0 & 11 \\ 0 & 0 & 0 & \frac{ 11 }{ 5 } & \frac{ 17 }{ 5 } \\ 0 & 0 & 11 & \frac{ 17 }{ 5 } & 30 \\ \end{array} \right) $$
==============================================
$$ E_{10} = \left( \begin{array}{rrrrr} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & - \frac{ 11 }{ 5 } \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) $$ $$ P_{10} = \left( \begin{array}{rrrrr} 0 & 1 & 4 & \frac{ 8 }{ 5 } & \frac{ 16 }{ 5 } \\ 1 & - \frac{ 1 }{ 5 } & - 2 & \frac{ 1 }{ 5 } & \frac{ 2 }{ 5 } \\ 0 & 0 & 1 & - \frac{ 8 }{ 5 } & - \frac{ 11 }{ 5 } \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{10} = \left( \begin{array}{rrrrr} \frac{ 1 }{ 5 } & 1 & \frac{ 6 }{ 5 } & \frac{ 7 }{ 5 } & \frac{ 8 }{ 5 } \\ 1 & 0 & - 4 & - 8 & - 12 \\ 0 & 0 & 1 & \frac{ 8 }{ 5 } & \frac{ 11 }{ 5 } \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{10} = \left( \begin{array}{rrrrr} 5 & 0 & 0 & 0 & 0 \\ 0 & - \frac{ 1 }{ 5 } & 0 & 0 & 0 \\ 0 & 0 & 5 & 0 & 0 \\ 0 & 0 & 0 & \frac{ 11 }{ 5 } & \frac{ 17 }{ 5 } \\ 0 & 0 & 0 & \frac{ 17 }{ 5 } & \frac{ 29 }{ 5 } \\ \end{array} \right) $$
==============================================
$$ E_{11} = \left( \begin{array}{rrrrr} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & - \frac{ 17 }{ 11 } \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) $$ $$ P_{11} = \left( \begin{array}{rrrrr} 0 & 1 & 4 & \frac{ 8 }{ 5 } & \frac{ 8 }{ 11 } \\ 1 & - \frac{ 1 }{ 5 } & - 2 & \frac{ 1 }{ 5 } & \frac{ 1 }{ 11 } \\ 0 & 0 & 1 & - \frac{ 8 }{ 5 } & \frac{ 3 }{ 11 } \\ 0 & 0 & 0 & 1 & - \frac{ 17 }{ 11 } \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{11} = \left( \begin{array}{rrrrr} \frac{ 1 }{ 5 } & 1 & \frac{ 6 }{ 5 } & \frac{ 7 }{ 5 } & \frac{ 8 }{ 5 } \\ 1 & 0 & - 4 & - 8 & - 12 \\ 0 & 0 & 1 & \frac{ 8 }{ 5 } & \frac{ 11 }{ 5 } \\ 0 & 0 & 0 & 1 & \frac{ 17 }{ 11 } \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{11} = \left( \begin{array}{rrrrr} 5 & 0 & 0 & 0 & 0 \\ 0 & - \frac{ 1 }{ 5 } & 0 & 0 & 0 \\ 0 & 0 & 5 & 0 & 0 \\ 0 & 0 & 0 & \frac{ 11 }{ 5 } & 0 \\ 0 & 0 & 0 & 0 & \frac{ 6 }{ 11 } \\ \end{array} \right) $$
==============================================
$$ P^T H P = D $$ $$\left( \begin{array}{rrrrr} 0 & 1 & 0 & 0 & 0 \\ 1 & - \frac{ 1 }{ 5 } & 0 & 0 & 0 \\ 4 & - 2 & 1 & 0 & 0 \\ \frac{ 8 }{ 5 } & \frac{ 1 }{ 5 } & - \frac{ 8 }{ 5 } & 1 & 0 \\ \frac{ 8 }{ 11 } & \frac{ 1 }{ 11 } & \frac{ 3 }{ 11 } & - \frac{ 17 }{ 11 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrrr} 0 & 1 & 2 & 3 & 4 \\ 1 & 5 & 6 & 7 & 8 \\ 2 & 6 & 9 & 10 & 11 \\ 3 & 7 & 10 & 12 & 13 \\ 4 & 8 & 11 & 13 & 14 \\ \end{array} \right) \left( \begin{array}{rrrrr} 0 & 1 & 4 & \frac{ 8 }{ 5 } & \frac{ 8 }{ 11 } \\ 1 & - \frac{ 1 }{ 5 } & - 2 & \frac{ 1 }{ 5 } & \frac{ 1 }{ 11 } \\ 0 & 0 & 1 & - \frac{ 8 }{ 5 } & \frac{ 3 }{ 11 } \\ 0 & 0 & 0 & 1 & - \frac{ 17 }{ 11 } \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrr} 5 & 0 & 0 & 0 & 0 \\ 0 & - \frac{ 1 }{ 5 } & 0 & 0 & 0 \\ 0 & 0 & 5 & 0 & 0 \\ 0 & 0 & 0 & \frac{ 11 }{ 5 } & 0 \\ 0 & 0 & 0 & 0 & \frac{ 6 }{ 11 } \\ \end{array} \right) $$ $$ Q^T D Q = H $$ $$\left( \begin{array}{rrrrr} \frac{ 1 }{ 5 } & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ \frac{ 6 }{ 5 } & - 4 & 1 & 0 & 0 \\ \frac{ 7 }{ 5 } & - 8 & \frac{ 8 }{ 5 } & 1 & 0 \\ \frac{ 8 }{ 5 } & - 12 & \frac{ 11 }{ 5 } & \frac{ 17 }{ 11 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrrr} 5 & 0 & 0 & 0 & 0 \\ 0 & - \frac{ 1 }{ 5 } & 0 & 0 & 0 \\ 0 & 0 & 5 & 0 & 0 \\ 0 & 0 & 0 & \frac{ 11 }{ 5 } & 0 \\ 0 & 0 & 0 & 0 & \frac{ 6 }{ 11 } \\ \end{array} \right) \left( \begin{array}{rrrrr} \frac{ 1 }{ 5 } & 1 & \frac{ 6 }{ 5 } & \frac{ 7 }{ 5 } & \frac{ 8 }{ 5 } \\ 1 & 0 & - 4 & - 8 & - 12 \\ 0 & 0 & 1 & \frac{ 8 }{ 5 } & \frac{ 11 }{ 5 } \\ 0 & 0 & 0 & 1 & \frac{ 17 }{ 11 } \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrr} 0 & 1 & 2 & 3 & 4 \\ 1 & 5 & 6 & 7 & 8 \\ 2 & 6 & 9 & 10 & 11 \\ 3 & 7 & 10 & 12 & 13 \\ 4 & 8 & 11 & 13 & 14 \\ \end{array} \right) $$