Es este determinante siempre no negativo?

Question

Para cualquier $(a_1,a_2,\cdots,a_n)\in\mathbb{R}^n$, una matriz $A$ se define por $$A_{ij}=\frac1{1+|a_i-a_j|}$$ Es $\det(A)$ siempre no negativo? Hice algunos test numérico y parece ser cierto, pero yo no tengo ni idea de cómo demostrarlo...

Gracias!

Answer 1

Aquí está una analítica de la prueba (que creo que he aprendido en otra parte, aunque no en esta forma). En primer lugar, muestran una expresión algebraica hecho:

Teorema 1. Deje que $\mathbb{K}$ ser un anillo conmutativo y dejar $n\in\mathbb{N} $. Deje de $p_{1},p_{2},\ldots,p_{n-1}$ ser $n-1$ elementos de $\mathbb{K}$. Para cualquier $\left( i,j\right) \en\left\{ 1,2,\ldots,n\right\} ^{2}$ satisfacer $i\leq j$ nos $a_{i,j}=\prod_{i=i}^{j-1}p_{r}=p_{i}p_{i+1}\cdots p_{j-1}$. (Cuando $i=j$, este producto está vacía y por lo tanto se evalúa a $1$.) Para cualquier $\left( i,j\right) \en\left\{ 1,2,\ldots,n\right\} ^{2}$ satisfacer $i>j$, hemos establecido $a_{i,j}=a_{j,i}$ (desde $a_{j,i}$ ya ha sido definido por el anterior la frase). Deje que $A$ ser $n\times n$-matriz $\left( a_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}$. Tenemos

$\det a=\prod_{i=1}^{n-1}\left( 1-p_{r}^{2}\right) $.

(Entendemos que la mano derecha vacía producto si $n$ es $0$ o $1$.)

(Ejemplo: Cuando $n=4$, la matriz $A$ en el Teorema 1 es igual a $\left( \begin{array} [c]{cccc} 1 & p_{1} & p_{1}p_{2} & p_{1}p_{2}p_{3}\\ p_{1} & 1 & p_{2} & p_{2}p_{3}\\ p_{1}p_{2} & p_{2} & 1 & p_{3}\\ p_{1}p_{2}p_{3} & p_{2}p_{3} & p_{3} & 1 \end{array} \right) $.)

La prueba del Teorema 1. En primer lugar, una anotación: Si $N\in\mathbb{N}$ y $M\in\mathbb{N}$, $B$ es un $N\times M$-matriz, y si $p\in\left\{ 1,2,\ldots,N\right\} $ y $p\in\left\{ 1,2,\ldots,M\right\} $, entonces nos vamos $B_{\sim p,\sim q}$ denotar el $\left( N-1\right) \times\left( M-1\right) $matriz obtenida a partir de la matriz $B$ cruzando el $p$-ésima fila y la $p$-ésima columna. Es bien sabido que si $K$ es un número entero positivo, y si la $K$-ésima fila de a $K\times K$-matriz $D$ es cero, aparte de su última entrada, luego

(1) $\det D=d\det\left( D_{\sim K,\sim K}\right) $,

donde $d$ es la última entrada de la $K$-ésima fila de $D$. (Esto puede ser visto como un caso particular de Laplace de expansión con respecto a la $K$-ésima fila).

Ahora, vamos a demostrar que

(2) $\det\left( \left( a_{i,j}\right) _{1\leq i\leq k,\ 1\leq j\leq k}\right) =\prod_{i=1}^{k-1}\left( 1-p_{r}^{2}\right) $ de cada $k\in\left\{ 0,1,\ldots,n\right\} $.

De hecho, podemos demostrar (2) por la inducción de más de $k$: Si $k=0$ o $k=1$, entonces (2) se sostiene por la inspección. Para la inducción de paso, arreglar $K\in\left\{ 2,3,\ldots,n\right\} $, y asumir (como la inducción de hipótesis) de que (2) sostiene por $k=K-1$. Ahora, si restamos los $p_{K-1}$ veces $\left( K-1\right) $-ésima fila de la matriz $\left( a_{i,j}\right) _{1\leq i\leq K,\ 1\leq j\leq K}$ de $K$-ésima fila, a continuación, obtenemos una nueva matriz $C$. Es es fácil ver que la $K$-ésima fila de la nueva matriz $C$ es cero, aparte de su última entrada, que es de $1-p_{K-1}^{2}$. Por lo tanto, (1) (aplicado a $D=C$) de los rendimientos de

(3) $\det C=\left( 1-p_{K-1}^{2}\right) \det\left( \underbrace{C_{\sim K,\sim K}}_{=\left( a_{i,j}\right) _{1\leq i\leq K-1,\ 1\leq j\leq K-1} }\right) $

$=\left( 1-p_{K-1}^{2}\right) \underbrace{\det\left( \left( a_{i,j} \right) _{1\leq i\leq K-1,\ 1\leq j\leq K-1}\right) }_{\substack{=\prod _{i=1}^{\left( K-1\right) -1}\left( 1-p_{r}^{2}\right) \\\text{(por el la inducción de la hipótesis)}}}$

$=\left( 1-p_{K-1}^{2}\right) \prod_{i=1}^{\left( K-1\right) -1}\left( 1-p_{r}^{2}\right) =\prod_{i=1}^{K-1}\left( 1-p_{r}^{2}\right) $.

Pero la matriz $C$ se obtuvo a partir de la matriz $\left( a_{i,j}\right) _{1\leq i\leq K,\ 1\leq j\leq K}$ por restar un múltiplo de una fila de otro (véase la definición de $C$); es sabido que dicha sustracción ¿ no cambiar el determinante de una matriz. Por lo tanto, $\det C=\det\left( \left( a_{i,j}\right) _{1\leq i\leq K,\ 1\leq j\leq K}\right) $. En comparación con (3), esto produce

$\det\left( \left( a_{i,j}\right) _{1\leq i\leq K,\ 1\leq j\leq K}\right) =\prod_{i=1}^{K-1}\left( 1-p_{r}^{2}\right) $,

y por lo tanto (2) tiene por $k=K$. Esto completa el paso de inducción, por lo que que (2) es probada.

Ahora, aplicando (2) $k=$ n, obtenemos $\det\left( \left( a_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}\right) =\prod_{i=1}^{n-1}\left( 1-p_{r} ^{2}\right) $. Dado que $A=\left( a_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}$, este vuelve a escribir como $\det a=\prod_{i=1}^{n-1}\left( 1-p_{r}^{2}\right) $. Teorema 1 sea probado.

Corolario 2. Deje de $q_{1},q_{2},\ldots,q_{n}$ $n$ distintas positiva de reales. Vamos a $w\ \ en\left[ 0,1\right) $. Entonces, $\det\left( \left( w^{\left\vert q_{i}-q_{j}\right\vert }\right) _{1\leq i\leq n,\ 1\leq j\leq n}\right) >0$.

La prueba del Corolario 2. Si queremos permutar los números $q_{1},q_{2},\ldots,q_{n}$ (entre sí), entonces la matriz $\left( w^{\left\vert q_{i} -q_{j}\right\vert }\right) _{1\leq i\leq n,\ 1\leq j\leq n}$ cambios, pero su determinante de $\det\left( \left( w^{\left\vert q_{i}-q_{j}\right\vert }\right) _{1\leq i\leq n,\ 1\leq j\leq n}\right) $ se mantiene sin cambios (debido a las filas de la matriz de obtener permutada, y para hacer las columnas, pero ambos los tiempos de uno y el mismo permutación se utiliza, por lo que los signos de cancelar). Por lo tanto, se puede WLOG suponga que $q_{1}<q_{2}<\cdots<q_{n}$ (podemos lograr esto mediante un permutación). Asumir esto, y $p_{r}=w^{q_{i+1}-q_{r}}$ para cada $i\in\left\{ 1,2,\ldots,n-1\right\} $. Observe que, por cada $i\in\left\{ 1,2,\ldots,n-1\right\} $, tenemos $p_{r}=w^{q_{i+1}-q_{r}}\in\left[ 0,1\right) $ (desde $w\ \ en\left[ 0,1\right) $ y $q_{i+1}-\underbrace{q_{r} }_{<q_{i+1}}>0$).

Conjunto $\mathbb{K}=\mathbb{R}$. Definir la matriz $A$ como en el Teorema 1. A continuación, se es fácil ver que $A=\left( w^{\left\vert q_{i}-q_{j}\right\vert }\right) _{1\leq i\leq n,\ 1\leq j\leq n}$. Pero Teorema 1 rendimientos de los

$\det a=\prod_{i=1}^{n-1}\underbrace{\left( 1-p_{r}^{2}\right) }_{\substack{>0\\\text{(desde }p_{r}\in\left[ 0,1\right) \text{)}}}>0$.

Dado que $A=\left( w^{\left\vert q_{i}-q_{j}\right\vert }\right) _{1\leq i\leq n,\ 1\leq j\leq n}$, este vuelve a escribir como $\det\left( \left( w^{\left\vert q_{i}-q_{j}\right\vert }\right) _{1\leq i\leq n,\ 1\leq j\leq n}\right) >0$. Corolario 2 está demostrado así.

Corolario 3. Deje de $q_{1},q_{2},\ldots,q_{n}$ $$ n distinta de reales. Vamos $w\ \ en\left[ 0,1\right) $. A continuación, el $n\times n$-matriz $\left( w^{\left\vert q_{i}-q_{j}\right\vert }\right) _{1\leq i\leq n,\ 1\leq j\leq n}$ es positiva definida.

La prueba del Corolario 3. Sylvester criterio de la certeza positiva dice que una matriz simétrica $\left( g_{i,j}\right) _{1\leq i\leq n,\ 1\leq j\leq n}\in\mathbb{R}^{n\times n}$ es positiva definida si y sólo si cada $k\in\left\{ 1,2,\ldots,n\right\} $ satisface $\det\left( \left( g_{i,j}\right) _{1\leq i\leq k,\ 1\leq j\leq k}\right) >0$. Podemos aplicar esta a $g_{i,j}=w^{\left\vert q_{i}-q_{j}\right\vert }$ (ya que la matriz $\left( w^{\left\vert q_{i}-q_{j}\right\vert }\right) _{1\leq i\leq n,\ 1\leq j\leq n}$ es simétrica), y así es probar que cada $k\in\left\{ 1,2,\ldots,n\right\} $ satisface $\det\left( \left( w^{\left\vert q_{i}-q_{j}\right\vert }\right) _{1\leq i\leq k,\ 1\leq j\leq k}\right) >0$. Pero esto sigue del Corolario 2 (aplicado a $k$ en lugar de $n$). Por lo tanto, el Corolario 3 está probada.

Teorema 4. Deje de $q_{1},q_{2},\ldots,q_{n}$ $$ n distinta de reales. A continuación, el $n\times n$-matriz $\left( \dfrac{1}{1+\left\vert q_{i} -q_{j}\right\vert }\right) _{1\leq i\leq n,\ 1\leq j\leq n}$ es positiva definida.

La prueba del Teorema 4. La matriz en cuestión es claramente simétrica. Por lo tanto, sólo tenemos que demostrar que $\sum_{i=1}^{n}\sum_{j=1} ^{n}\dfrac{1}{1+\left\vert q_{i}-q_{j}\right\vert }x_{i}x_{j}>0$ por cada distinto de cero vector $\left( x_{1},x_{2},\ldots,x_{n}\right) \in\mathbb{R}^{n}$.

Por lo tanto, fijar un vector distinto de cero $\left( x_{1},x_{2},\ldots,x_{n}\right) \in\mathbb{R}^{n}$. Por cada $w\ \ en\left[ 0,1\right) $ tenemos $\sum _{i=1}^{n}\sum_{j=1}^{n}w^{\left\vert q_{i}-q_{j}\right\vert }x_{i}x_{j}>0$ (por el Corolario 3). Ahora,

$\sum_{i=1}^{n}\sum_{j=1}^{n}\underbrace{\dfrac{1}{1+\left\vert q_{i} -q_{j}\right\vert }}_{\substack{=\int_{0}^{1}w^{\left\vert q_{i} -q_{j}\right\vert }dw\\\text{(ya que }\left\vert q_{i}-q_{j}\right\vert \geq0\text{)}}}x_{i}x_{j}$

$=\sum_{i=1}^{n}\sum_{j=1}^{n}\left( \int_{0}^{1}w^{\left\vert q_{i} -q_{j}\right\vert }dw\right) x_{i}x_{j}$

$=\int_{0}^{1}\underbrace{\left( \sum_{i=1}^{n}\sum_{j=1}^{n}w^{\left\vert q_{i}-q_{j}\right\vert }x_{i}x_{j}\right) }_{>0}dw>0$.

Esto es precisamente lo que quería mostrar, y por lo tanto el Teorema 4 sea probado.

Corolario 5. Deje de $q_{1},q_{2},\ldots,q_{n}$ $n$ reales. A continuación, el $n\times n$-matriz $\left( \dfrac{1}{1+\left\vert q_{i}-q_{j}\right\vert }\right) _{1\leq i\leq n,\ 1\leq j\leq n}$ es positivo-semidefinite.

La prueba del Corolario 5. Esto puede ser derivado de Corolario 4 por la continuidad (porque siempre es posible deformar nuestra $n$ reales $q_{1},q_{2} ,\ldots,q_{n}$ en $n$ distintos reales). Un argumento alternativo sería el uso de la semidefinite analógica de Sylvester criterio positivo la certeza. (Debe advertirse, sin embargo, que este análogo requiere que todos los principales los menores a $\geq0$, en lugar de sólo el líder principal de los menores de edad!)

Answer 2

Esta respuesta es una sugerencia en cuanto a cómo usted puede probar el resultado, pero no contiene una prueba. En su lugar, voy a mostrar cómo un problema similar ha sido contestadas, y la oferta de punteros a las reclamaciones que mostrar su resultado:

Considere la matriz: $$A_{ij} = \frac{1}{1 + |a_i - a_j|^2}$$ En última instancia, vamos a encontrar que $\det(A)$ es siempre no negativo. La razón es que $a$ en sí es una matriz positiva definida. Es en la familia de la Racional Cuadrática Función de Covarianza: (también conocido como T de Student Kernel)

El racional cuadrática de la covarianza entre dos puntos separados por una distancia d de las unidades está dada por $$C_{RQ}(d) = \Bigg(1+\frac{d^2}{2\alpha k^2}\Bigg)^{-\alpha}$$ En este caso, $\alpha = 1$, $k = \frac{\sqrt{2}}{2}$.

---

(De Wikipedia): La Función de Covarianza de un espacio en proceso $Z(x)$ es definido por $$C(x, y) = \textrm{Cov}(Z(x), Z(y))$$ Para las ubicaciones de $x_1, x_2, \ldots, x_N \D$ la varianza de cada combinación lineal: $$X=\sum_{i=1}^N w_i Z(x_i)$$ puede calcularse como $$\operatorname{var}(X)=\sum_{i=1}^N \sum_{j=1}^N w_i C(x_i,x_j) w_j$$ Una función válida es la covarianza de la función si y sólo si esta variación es no negativo para todas las opciones posibles de $N$ y pesos $w_1, \ldots, w_N$. Una función con esta propiedad se llama positiva definida.

Para este problema en particular, los $x_i$ en la declaración son los $a_i$ en la matriz $A$ se define anteriormente, y $C(x_i, x_j) = C_{RQ}(|a_i - a_j|)$. Es bien conocido (ver más abajo) que $C_{RQ}$ es positiva definida como se define anteriormente, y así para cada combinación lineal: $$\sum_{i=1}^N \sum_{j=1}^N w_i C_{RQ}(|a_i - a_j|) w_j \geq 0$$ es decir, $A$ es positiva definida.

Algunas referencias para el de arriba (incluida la declaración de que $C_{RQ}$ es positiva definida) puede ser visto en: Gauss Procesos para el Aprendizaje de Máquina Rasmussen, Williams 2006 y Clases de Granos para la Máquina de Aprendizaje: Estadística Perspectiva Genton de 2001.

Ahora el kernel correspondiente a la matriz está interesado en que ha sido referido como la Generalizada T de Student Kernel. $$C(x, y) = \frac{1}{1 + |x - y|^d}$$ En ese blog, la siguiente "prueba" que se ofrece:

La generalización de la T-Student Kernel ha sido demostrado ser un Mercel Kernel, por lo tanto tener una actitud positiva semi-definida Núcleo de la matriz (Boughorbel, 2004).

El papel que se hace referencia es Condicionalmente Positiva Definida Kernels Para SVM Imagen Basada en el Reconocimiento - Boughorbel, Tarel, Boujemaa Si esto resulta ser cierto, entonces el determinante de la matriz es, de hecho, no negativo.

Answer 3

OK me lo imaginé a mí mismo... alguien por favor revise si este es el correcto

En lugar de la prueba de $Un$ ha no negativo determinante, podemos probar realmente es positivo semidefinite. La prueba se hace por inducción sobre $n$, y todo lo que necesitamos para demostrar que $\det(A)\ge0$. La primera nota que permuting $a_1,\cdots,a_n$, o la adición de una constante para todos ellos, no cambia el PSD-dad de $A$, por lo que podemos suponer $a_1\ge a_2\ge \cdots\ge a_n=1$.

A partir de esto podemos simplificar $A$ en $$A=\left( \begin{array}{cccc} 1 & \dfrac1{1+a_1-a_2} & \cdots & \dfrac1{a_1} \\ \dfrac1{1+a_1-a_2} & 1 & \cdots & \dfrac1{a_2} \\ \vdots & \vdots & \ddots & \vdots \\ \dfrac1{a_1} & \dfrac1{a_2} & \cdots & 1 \end{array}\right)$$

por lo que $$\det(A)=\left| \begin{array}{cccc} 1-\dfrac1{a_1^2} & \dfrac1{1+a_1-a_2}-\dfrac1{a_1a_2} & \cdots & \dfrac1{1+a_1-a_{n-1}}-\dfrac1{a_1a_{n-1}} \\ \dfrac1{1+a_1-a_2}-\dfrac1{a_1a_2} & 1-\dfrac1{a_2^2} & \cdots & \dfrac1{1+a_2-a_{n-1}}-\dfrac1{a_2a_{n-1}} \\ \vdots & \vdots & \ddots & \vdots \\ \dfrac1{1+a_1-a_{n-1}}-\dfrac1{a_1a_{n-1}} & \dfrac1{1+a_2-a_{n-1}}-\dfrac1{a_2a_{n-1}} & \cdots & 1-\dfrac1{a_{n-1}^2} \end{array}\right| =\left| \begin{array}{cccc} 1\cdot\dfrac{a_1-1}{a_1}\cdot\dfrac{a_1+1}{a_1} & \dfrac1{1+a_1-a_2}\cdot\dfrac{a_2-1}{a_2}\cdot\dfrac{a_1+1}{a_1} & \cdots & \dfrac1{1+a_1-a_{n-1}}\cdot\dfrac{a_{n-1}-1}{a_n}\cdot\dfrac{a_1+1}{a_1} \\ \dfrac1{1+a_1-a_2}\cdot\dfrac{a_2-1}{a_2}\cdot\dfrac{a_1+1}{a_1} & 1\cdot\dfrac{a_2-1}{a_2}\cdot\dfrac{a_2+1}{a_2} & \cdots & \dfrac1{1+a_2-a_{n-1}}\cdot\dfrac{a_{n-1}-1}{a_n}\cdot\dfrac{a_2+1}{a_2} \\ \vdots & \vdots & \ddots & \vdots \\ \dfrac1{1+a_1-a_{n-1}}\cdot\dfrac{a_{n-1}-1}{a_{n-1}}\cdot\dfrac{a_1+1}{a_1} & \dfrac1{1+a_2-a_{n-1}}\cdot\dfrac{a_{n-1}-1}{a_{n-1}}\cdot\dfrac{a_2+1}{a_2} & \cdots & 1\cdot\dfrac{a_{n-1}-1}{a_{n-1}}\cdot\dfrac{a_{n-1}+1}{a_{n-1}} \end{array}\right| =\det(\left( \begin{array}{cccc} 1 & \dfrac1{1+a_1-a_2} & \cdots & \dfrac1{1+a_1-a_{n-1}} \\ \dfrac1{1+a_1-a_2} & 1 & \cdots & \dfrac1{1+a_2-a_{n-1}} \\ \vdots & \vdots & \ddots & \vdots \\ \dfrac1{1+a_1-a_{n-1}} & \dfrac1{1+a_2-a_{n-1}} & \cdots & 1 \end{array}\right) \circ \left( \begin{array}{cccc} \dfrac{a_1-1}{a_1} & \dfrac{a_2-1}{a_2} & \cdots & \dfrac{a_{n-1}-1}{a_n} \\ \dfrac{a_2-1}{a_2} & \dfrac{a_2-1}{a_2} & \cdots & \dfrac{a_{n-1}-1}{a_n} \\ \vdots & \vdots & \ddots & \vdots \\ \dfrac{a_{n-1}-1}{a_{n-1}} & \dfrac{a_{n-1}-1}{a_{n-1}} & \cdots & \dfrac{a_{n-1}-1}{a_{n-1}} \end{array}\right) \circ \left( \begin{array}{cccc} \dfrac{a_1+1}{a_1} & \dfrac{a_1+1}{a_1} & \cdots & \dfrac{a_1+1}{a_1} \\ \dfrac{a_1+1}{a_1} & \dfrac{a_2+1}{a_2} & \cdots & \dfrac{a_2+1}{a_2} \\ \vdots & \vdots & \ddots & \vdots \\ \dfrac{a_1+1}{a_1} & \dfrac{a_2+1}{a_2} & \cdots & \dfrac{a_{n-1}+1}{a_{n-1}} \end{array}\right)) $$

donde $\circ$ es el producto de Hadamard.

Ahora por la inducción de la primera matriz es PSD, y es fácil comprobar la segunda y la tercera son PSD así desde $\dfrac{a_i-1}{a_i}\ge\dfrac{a_j-1}{a_j}$ y $\dfrac{a_i+1}{a_i}\le\dfrac{a_j+1}{a_j}$ para $i\lt j$, así que por Schur producto teorema de que su producto es PSD, por lo que $\det(A)\ge0$, lo que completa la inducción.