[Math] Generate integer matrices with integer eigenvalues

eigenvalues-eigenvectorslinear algebramatricesorthogonal matricesrandom matrices

I want to generate $500$ random integer matrices with integer eigenvalues.

Thanks to this post, I know how to generate a random matrix with whole eigenvalues:

  1. Generate a diagonal matrix $D$ with the desired (integer)
    eigenvalues.

  2. Generate an invertible matrix $A$ of the same size as $D$.

  3. Record the matrix $A^{-1} D A$.

However, the problem is that this generates a lot of float matrices, and I'd actually like to have both integer matrices and integer eigenvalues.

The float values are introduced by A.inverse(). According to this post, inverse matrices have whole integer values only when the determinant of the original matrix is 1 or -1 (and therefore an orthogonal matrix).

I tried using the C++ library AlgLib, which has a rmatrixrndorthogonal function that uses G.W. Stewart's 1980 algorithm to generate a random uniformly distributed (Haar) orthogonal matrix. I also tried using R's pracma library, which has a randorthofunction that also generates orthogonal matrices. However, both functions generate matrices with float values.

Is there a way for me to generate orthogonal, integer matrices?

Best Answer

Let $x$ be a column of our desired orthogonal integer matrix.

To satisfy the condition that $$\sum_{i=1}^n x_i^2=1$$ where $x_i \in \mathbb{Z}$

we require exactly one $x_i$ to satisfy $|x_i|=1$ and $x_j = 0, j \neq i$.

Hence the columns of such matrices consists of $\{\pm e_1, \ldots, \pm e_n \}$ where $e_i$ is the standard unit vectors.

Remark:

Suppose $P$ is one such matrix. and suppose $Pe_i = \pm e_j$,

$$e_i^T PDP^Te_i=e_j^TDe_j=d_j$$

Hence you are just permutating the diagonal entries.

Schur decomposition might be of interest to you.

Related Question