Cómo aleatoriamente construir un cuadrado completo del ranking de la matriz con bajo factor determinante?

Question

Cómo aleatoriamente construir un cuadrado (1000*1000) total del ranking de la matriz con bajo factor determinante?

He probado el método siguiente, pero no pudo.

En MATLAB, yo sólo uso:

n=100;

A=randi([0 1], n, n);

mientras el rango(A)~=n

A=randi([0 1], n, n);

final

El código anterior genera un azar de la matriz binaria, con la esperanza de que el correspondiente factor determinante puede ser pequeña.

Sin embargo, el factor determinante es generalmente de alrededor de 10^49, un número enorme.

Por no hablar de cuando n>200, el factor determinante es generalmente desbordó en MATLAB.

Podría alguien tiene comentarios ¿cómo puedo generar la matriz (podría ser no-binario) con muy baja determinante (por ejemplo, <10^3)?

Answer 1

Una posibilidad: la de Generar un triangular inferior de la matriz con unos en la diagonal. Generar un triangular superior de la matriz con unos en la diagonal. Las múltiples sería una matriz con determinante de uno.

Esto sería un poco no aleatoria cuando inspeccionado como la esquina inferior derecha de los elementos sería mayor que en la parte superior izquierda. Pero la idea le da control sobre lo determinante que obtenga. Usted podría escala de las matrices triangulares adecuadamente elementwise para compensar.

Segunda posibilidad: Si se desea calcular una inversa (tal vez sólo generar una matriz inversa y alguna otra manera menos costosa) y luego hacer $PDP^{-1}$ y el resultado ha determinante mismo como $D$ una matriz diagonal. Tenga cuidado de no utilizar $D=I$ ya que sólo se puede obtener la identidad de nuevo.

Tercera posibilidad: la de realizar azar elementales por filas en la matriz de identidad (o de otro $D$ deseado determinante.)

Answer 2

El determinante de a $e^B$ $e^{\textrm{tr}(B)}$ (wiki) y $e^B$ siempre es invertible, ya que $e^B e^{-B}=\textrm{Id}$. Por lo tanto, si usted tiene una matriz de $B$ con la negativa de seguimiento, a continuación, $\det e^B$ es positivo y menor que $1$. El uso de esta idea que me escribió la siguiente secuencia de comandos de matlab que genera las matrices con los "pequeños" determinante:

n=100;
for i=1:10
    B=randn(n);
    A=expm(B);
    det(A)
end

Puedo generar los coeficientes mediante una distribución normal con media de $0$, por lo que la espera de la traza de B es $0$ (creo) y por lo tanto la espera determinante de $A$$1$.

Answer 3

Aquí es una manera de generar completo rango 0-1 matrices aleatorias con el tamaño absoluto de los determinantes. Vamos a adoptar de Matlab notaciones para la fila/columna de la indización. Supongamos que el objetivo de la matriz de $A$$n\times n$. A partir de experimentos numéricos, podemos ver que la media del valor absoluto del determinante de una random $20\times20$ de la matriz binaria es acerca de $3600$, cuyo orden de magnitud es acerca de la OP deseada de límite superior. Así que la idea es comenzar con un $k\times k$ matriz aleatoria con $k\le20$ y el mínimo absoluto determinante, a continuación, expanda a un $n\times n$ total rango de la matriz con la misma absoluta determinante. Los detalles son como sigue:

1. Inicializar $A$ a la matriz cero.
2. Elija un tamaño al azar $k\in\{1,2,\ldots,20\}$ y establezca $A(1:k,\,1:k)$ al azar a una 0-1 de la matriz. Repita este paso hasta que $|\det A(1:k,\,1:k)|$ es distinto de cero y menor que el necesario límite superior. (Usted puede usar una muestra ponderada de $k$ para ajustar la distribución de la absoluta determinante.)
3. Para $m=k+1,\ldots,n$, generan la última fila y la última columna de la submatriz $A(1:m,\,1:m)$ como sigue:
   1. Escoger un número al azar en $\{0,1\}$.
   2. Si el resultado es $0$, haga lo siguiente:
      1. Escoge un índice de columna $j\in\{1,\,\ldots,\,m-1\}$ al azar.
      2. Set $A(1:(m-1),\,m)=A(1:(m-1),\,j)$ y establezca $A(m,m)=1$.
      3. Para cada una de las $k\in\{1,\,\ldots,\,m-1\}$$k\not=j$, aleatoriamente ($A(m,k)=0$ o $1$.
      4. Permutar las columnas de a $A(1:m,\,1:m)$ al azar. O puede que simplemente el intercambio de $A(1:m,\,m)$ con $A(1:m,\,k)$ donde $k\in\{1,\,\ldots,\,m-1\}$ es elegido al azar.
   3. Si el resultado es $1$, realice el procedimiento análogo al paso 3.2 en una "transposición" de la moda. En otras palabras, el primer set $A(m,\,1:(m-1))$ lo que equivale a unos $A(i,\,1:(m-1))$$A(m,m)=1$, entonces el conjunto de las entradas de $A(m,:)$ (a excepción de la $i$-th uno y el $m$-th) a $0$ o $1$ al azar. A continuación, permutar las filas de $A(1:m,\,1:m)$ al azar.

He corrido un experimento numérico en mi equipo para generar 0-1 matrices de orden de 100. Si $A$ es de los elegidos completamente al azar, el promedio absoluto determinante más de 1000 muestras es de alrededor de $2.4\times10^{49}$. Con el procedimiento anterior, sin embargo, el promedio absoluto determinante es sólo $97.6$ cuando el impuesto límite superior es $1000$.