7
$\begingroup$

Key Problem : Is there any theorem about eigenvalues or positive semi-definiteness of small size matrices with small integer elements?

I have to check positive semi-definiteness of many symmetric matrices with integer elements. First I used eigenvalues, but floating point round error happens : eig(in numpy) sometimes gives small negative eigenvalues when a matrix is actually positive semi-definite.

I know Sylvester's criterion for positive semi-definiteness can avoid this problem. But I really don't want to use it since it requires computation of determinant of all principal minors, and I have to deal with really many matrices($ > 10^{20}$). I have to do anything to reduce number of calculations.

All the elements are integer and have small absolute values($\ <3 $), sizes of matrices are also small($\ < 10 \times 10 $). It seems pretty good condition, so I believe someone already researched this kind of matrices. Does anyone know useful theorems for this situation?

P.S: I'm pretty newbie in English Internet community and not native English speaker. So if you find something awkward, pardon me and let me know.

Improve this question
$\endgroup$
6
  • 5
    $\begingroup$ If you really need to deal with $10^{20}$ matrices, it is hopeless no matter what algorithm you use. $\endgroup$
    – Igor Rivin
    Commented Feb 13, 2018 at 19:55
  • $\begingroup$ I'm trying to use GPU to deal with large number, but I agree there's little hope :( Anyway I should try, and at least I can get intermediate results. $\endgroup$
    – SIM2
    Commented Feb 13, 2018 at 19:59
  • $\begingroup$ You don't have to check all $2^n$ principal minors, but only the $n$ leading principal minors, i.e., those using the first $i$ rows and first $i$ columns for $1\leq i\leq n$ $\endgroup$
    – Richard Stanley
    Commented Feb 13, 2018 at 20:10
  • 1
    $\begingroup$ @RichardStanley I believe it only works on positive definite matrices, according to web.archive.org/web/20170107084552/http://… . $\endgroup$
    – SIM2
    Commented Feb 13, 2018 at 20:24
  • $\begingroup$ @user531150 You are correct. I was thinking only of positive definite matrices. $\endgroup$
    – Richard Stanley
    Commented Feb 13, 2018 at 22:19

3 Answers 3

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Using relationship between roots of polynomials and coefficients! Although it will need some dirty calculations(I have to deal with 10x10 matrices XD), I really love this answer. Thanks! $\endgroup$
    – SIM2
    Commented Feb 14, 2018 at 0:42
  • $\begingroup$ But computing the characteristic polynomial is no cheaper than computing the principal minors, alas. $\endgroup$
    – Igor Rivin
    Commented Feb 14, 2018 at 0:44
  • $\begingroup$ @IgorRivin There might be some shorcuts to calculate coefficients of the characteristic polynomial numerically, just like in case of determinant using LU decomposition... but it seems like another tough question. Anyway this clearly avoids eigenvalues of +- 9e-9, and it means I don't have to worry making wrong answer. $\endgroup$
    – SIM2
    Commented Feb 14, 2018 at 1:05
5
$\begingroup$

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.

  1. Tridiagonalization: https://math.byu.edu/~schow/resources/householder.pdf
  2. Recurrence: https://en.m.wikipedia.org/wiki/Tridiagonal_matrix
Improve this answer
$\endgroup$
8
  • $\begingroup$ I have to make sure that I need positive 'semi'-definiteness, not just definiteness.Householder reflection preserves positive semi-definiteness, not only positive definiteness? Thanks for your answer! $\endgroup$
    – SIM2
    Commented Feb 13, 2018 at 21:14
  • $\begingroup$ But I'm not sure that I can avoid floating-point error if I use $\epsilon $. The reason I prefer Sylvester's criterion is that I can ensure determinant of integer matrix is integer, so use $\ round(det(M))$ instead of $\ det(M)$. I can still use reflections, thanks for your answer again. $\endgroup$
    – SIM2
    Commented Feb 13, 2018 at 21:34
  • $\begingroup$ I edited the post to handle semidefiniteness more efficiently. $\endgroup$
    – Geoffrey Irving
    Commented Feb 13, 2018 at 21:44
  • $\begingroup$ I'm not sure considering minors given by intervals is enough. Diagonal matrix of (0,-1,0,...) looks like a counterexample. Maybe additionally checking diagonal elements gives wanted results, but it will be really thankful if you give me a reference. $\endgroup$
    – SIM2
    Commented Feb 13, 2018 at 23:07
  • $\begingroup$ If you have a diagonal matrix with a -1, the interval minor that is just -1 will have negative determinant -1. In general, the determinant of any minor of a tridiagonal matrix will be a product of determinants of minors of intervals. If all interval minors are nonnegative, all their products will be. $\endgroup$
    – Geoffrey Irving
    Commented Feb 13, 2018 at 23:10
2
$\begingroup$

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) $$

Improve this answer
$\endgroup$
2
  • $\begingroup$ No need to calculate eigenvalues and only using rational(actually can be done in integer)! I really appreciate your answer. $\endgroup$
    – SIM2
    Commented Feb 14, 2018 at 0:47
  • $\begingroup$ @user531150 yes, it could be done with integers, but then there would not be the automatic production of $Q = P^{-1}.$ Anyway, output is Latex, code is C++ with GMP. Meanwhile, I suggest you do read a little on Sylvester's Law of Inertia, en.wikipedia.org/wiki/Sylvester's_law_of_inertia $\endgroup$
    – Will Jagy
    Commented Feb 14, 2018 at 0:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .