Generar matrices de enteros con valores propios enteros

Question

Quiero generar $500$ entero aleatorio matrices con números enteros autovalores.

Gracias a este post, yo sé cómo generar una matriz aleatoria con toda la autovalores:

1. Generar una matriz diagonal $D$ con la deseada (entero) autovalores.

2. Generar una matriz invertible $A$ del mismo tamaño como $D$.

3. Registro de la matriz $A^{-1} D A$.

Sin embargo, el problema es que esto genera una gran cantidad de float matrices, y en realidad me gustaría tener ambas matrices de enteros y enteros autovalores.

Los valores de coma flotante son introducidos por A.inverse(). De acuerdo con este post, matrices inversas tienen todo el entero de los valores sólo cuando el determinante de la matriz original es 1 o -1 (y por lo tanto una matriz ortogonal).

He intentado utilizar la C++ biblioteca AlgLib, que tiene un rmatrixrndorthogonal función que utiliza G. W. Stewart 1980 algoritmo para generar una aleatorios uniformemente distribuidos (Haar) ortogonal de la matriz. También he intentado usar R's pracma biblioteca, que tiene un randorthofunción que también genera ortogonal de matrices. Sin embargo, ambas funciones generar matrices con valores de coma flotante.

Hay una manera para mí para generar ortogonal, entero matrices?

Answer 1

Deje $x$ ser una columna de nuestra deseada ortogonal entero de la matriz.

Para satisfacer la condición de que $$\sum_{i=1}^n x_i^2=1$$ where $x_i \in \mathbb{Z}$

requerimos exactamente un $x_i$ a satisfacer $|x_i|=1$$x_j = 0, j \neq i$.

Por lo tanto las columnas de tales matrices se compone de $\{\pm e_1, \ldots, \pm e_n \}$ donde $e_i$ es el estándar de la unidad de vectores.

Comentario:

Supongamos $P$ es uno de esos matriz. y supongamos $Pe_i = \pm e_j$,

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

Por lo tanto usted está a solo permutating la diagonal entradas.

Schur de descomposición podrían ser de interés para usted.

Answer 2

Si sólo desea ortogonal de matrices, es super fácil. Aquí es un uniforme procedimiento de muestreo para todos los $n\times n$ entero ortogonal de matrices:

1. Permutar el conjunto de índices $\{1,2,\ldots,n\}$ al azar (usando, por ejemplo, Fisher-Yates shuffle). Que nos llame a los índices permutados $\{\sigma(1),\sigma(2),\ldots,\sigma(n)\}$.
2. Asignar un $n\times n$ cero de la matriz $A$. A continuación, para$i=1,2,\ldots,n$, $(i,\sigma(i))$- ésima (o, la $(\sigma(i),i)$-ésima si la matriz de los usos principales de la columna de indización; por supuesto, también es necesario hacer los ajustes correspondientes si la matriz de usos de base cero de la indización en lugar de uno basado en la indexación) de $A$ $+1$o $-1$ al azar.

Answer 3

Matrices orthogonal con valores enteros pueden tener sólo las entradas $1,0 ,-1$. Cada matriz que tiene sólo exactamente una entrada $= +1$ $-1$ en una columna y una fila donde las entradas de resto son ceros es ortogonal.
Fácil comprobar que productos de columnas (o filas) en este caso son siempre igual $0$ y normas para las columnas (filas) son igual $1$.

El ejemplo $\begin{bmatrix} 0 & 1 & 0 & 0 \\ -1 & 0 & 0 & 0 \\ 0 & 0 & -1 & 0\\ 0 & 0 & 0 & 1 \end{bmatrix}$ $\dots$

Answer 4

Pregunta 1. ¿Qué entiende usted por "quiero generar entero ALEATORIO matrices con números enteros autovalores" ?

Parece ser una pregunta difícil. Deje $Z$ ser el subconjunto de $M_n(\mathbb{Z})$ constituido de las matrices que han entero de sólo autovalores.

Paso 1. Es fácil: sea G ser un $N\times N$ real de la matriz cuyas entradas son independientes idénticamente distribuidas aleatoria normal estándar de las variables de $G_{i,j}\sim N(0,1)$ (cf. Ginibre 1965).

Paso 2. Por supuesto, podemos elegir una similar discretas de probabilidad, medida a lo largo de $\mathbb{Z}$ al azar y construir elementos de $M_n(\mathbb{Z})$. Sigue para obtener las matrices con valores propios en $\mathbb{Z}$.

Por desgracia, si $U_N$ es el número real de los autovalores de una matriz $G$ (paso 1), a continuación, $E(U_N)=\sqrt{2N/\pi}+O(1)$ al $N\rightarrow +\infty$; aquí queremos $N$ real de los autovalores! Por otra parte el real de los autovalores de una matriz $G$ no puede ser elegido al azar: cf. por ejemplo https://arxiv.org/abs/1512.01449

Entonces tenemos dos problemas: * ¿cuál es la probabilidad de medida inducida por $M_n(\mathbb{Z})$$Z$ ?

Por otro lado, podemos escribir nuestra matriz $A=P^{-1}DP$ donde $D$ es un número entero de la diagonal de la matriz (si $A$ tiene múltiples valores propios, entonces podemos optar $D$ como una matriz triangular; cf. a continuación); porque de lo que está escrito arriba, yo creo que * la diagonal de $D$ no puede ser elegido al azar.

Pregunta 2. Supongamos que hemos resuelto el problema de la elección de $D$$P^{-1}DP$. Entonces, ¿cómo elegir a $P$, de modo que $P^{-1}DP\in M_n(\mathbb{Z})$ ? La forma más sencilla es la de imponer $P\in SL_n(\mathbb{Z})$ (las matrices con $\det=-1$ son inútiles). Tenga en cuenta que la matriz de $\begin{pmatrix}-4&8\\-3&6\end{pmatrix}$ no puede ser escrito $P^{-1}diag(0,2)P$ donde $P\in SL_2(\mathbb{Z})$ pero puede ser escrito $P^{-1}DP$ donde $D$ es triangular. Por lo tanto, es mejor que elija $D$ triangular; no sé si cada matriz en $Z$ puede ser escrito $P^{-1}DP$ donde $P\in SL_n(\mathbb{Z})$ $D$ triangular en $M_n(\mathbb{Z})$. Si por la extraordinaria, la respuesta es sí, entonces se mantiene al azar para obtener un elemento $P\in SL_n(\mathbb{Z})$.

• $SL_n(\mathbb{Z})$ es generado por el transvections. A continuación, podemos elegir aleatoriamente transvections $I_N\pm E_{i,j}$ y consideran que su producto; creo que si $N$ es grande, entonces debemos considerar muchos transvections.

*También podemos escribir $A=L_1U_1L_2U_2\cdots$ cuando la $L_i$ (resp. el $U_i$) se triangular inferior (resp. superior triangular) con elementos de la diagonal $\pm 1$; no creo que esta aleatoriedad es muy buena, pero es fácil escribir!