Maximizar el rastro de forma elegante

Question

Supongamos que $\Lambda = {\rm diag}(\lambda_1,\cdots,\lambda_n)$ , $\Sigma = {\rm diag}(\sigma_1,\cdots,\sigma_n)$ y tenemos $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n \geq 0$ y $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_n \geq 0$ . Quiero demostrar que $${\rm max}[ {\rm Tr}(O^{\rm T}\Lambda O \Sigma)] = \sum_{i=1}^n \lambda_i \sigma_i,$$ donde $OO^{\rm T} = I$ . Un enfoque consiste en maximizar la función $$f(o_{ij}) = \sum_{i,j} \lambda_i (o_{ij})^2 \sigma_j$$ bajo la restricción $\sum_{k} o_{ik}o_{jk} = \delta_{ij}$ por el método del multiplicador de Lagrange. Puedo demostrar el enunciado de esta manera, pero toda la demostración es larga y carece del sabor del álgebra lineal. Como la afirmación "debe ser cierta" intuitivamente, quiero saber si hay una forma elegante de demostrarla. Una posible manera puede ser la inducción matemática pero no la he conseguido. Se agradece cualquier ayuda.

Answer 1

(Reescrito a partir de la última parte de mi respuesta a Minimización de rastros con restricciones .)

Como la función objetivo es continua y el conjunto de todas las matrices ortogonales reales es compacto, la traza máxima es continua en las entradas de $\Sigma$ . Por lo tanto, pasando al límite, podemos suponer sin pérdida de generalidad que $\Sigma$ tiene distintivo entradas diagonales.

La matriz exponencial de toda matriz asimétrica es una matriz real ortogonal de determinante uno. Si $O$ es un maximizador global en su problema, el valor de su función objetivo debe ser mayor o igual que el valor de la función objetivo evaluado en $Oe^{tK}$ (que es ortogonal real) para cualquier número real $t$ y cualquier simetría sesgada $K$ . Así, si definimos $f(t)=\operatorname{tr}(e^{-tK}O^T\Lambda Oe^{tK}\Sigma)$ Debemos tener $f'(0)=0$ . Utilizando la propiedad cíclica $\operatorname{tr}(XY)=\operatorname{tr}(YX)$ obtenemos $$0=f'(0)=\operatorname{tr}\left((\Sigma O^T\Lambda O-O^T\Lambda O\Sigma)\, K\right).$$ Poner $K^T=\Sigma O^T\Lambda O-O^T\Lambda O\Sigma$ (que sí es asimétrico), obtenemos $\operatorname{tr}(K^TK)=0$ . Por lo tanto, $K=0$ lo que significa que $O^T\Lambda O$ se desplaza con $\Sigma$ . Cualquier matriz que conmute con una matriz diagonal con entradas diagonales distintas debe tener todas las entradas no diagonales iguales a cero. Por lo tanto, $O^T\Lambda O$ es una matriz diagonal.

Por lo tanto, $\Lambda_1:=O^T\Lambda O$ es una permutación diagonal de $\Lambda$ porque $\Lambda_1$ y $\Lambda$ son matrices diagonales con los mismos valores propios. Ahora el problema se reduce a encontrar la permutación diagonal $\Lambda_1$ de $\Lambda$ que maximiza $\operatorname{tr}(\Lambda_1\Sigma)$ . Obviamente, el máximo se produce cuando $\Lambda_1=\Lambda$ o cuando $O=I$ .

Answer 2

Esto no es una respuesta.

Mi contribución consiste en mostrar que la cuestión es equivalente a una minimización de una cierta diferencia (en el sentido de la norma de Frobenius) todavía sobre todas las matrices ortogonales en un contexto aparentemente más general. Me hubiera gustado que este equivalente permitiera establecer el resultado, pero no lo he conseguido.

$$\begin{eqnarray}\tag{*}M&=&\min_{O \in O(n)}\|O^{\rm T}\Lambda O - \Sigma \|_F^2\\&=&\min_{O \in O(n)}{\rm Tr}[(O^{\rm T}\Lambda O - \Sigma)^T(O^{\rm T}\Lambda O - \Sigma)]\\&=&\min_{O \in O(n)}{\rm Tr}[\Lambda^2+\Sigma^2-(O^{\rm T}\Lambda O \Sigma)-(\Sigma O^{\rm T}\Lambda O)]\\&=&\min_{O \in O(n)}\left\{{\rm Tr}[\Lambda^2+\Sigma^2]-{\rm Tr}[(O^{\rm T}\Lambda O \Sigma)]-{\rm Tr}[(\Sigma O^{\rm T}\Lambda O)]\right\}\\\tag{1}&=&\min_{O \in O(n)}\left\{{\rm Tr}[\Lambda^2+\Sigma^2]-2 \ {\rm Tr}[(O^{\rm T}\Lambda O \Sigma)]\right\}\end{eqnarray}$$

Explicación: ${\rm Tr}[(\Sigma O^{\rm T}\Lambda O)]= {\rm Tr}[(O^{\rm T}\Lambda O \Sigma)]$ debido a la siguiente "propiedad circulante" del operador de traza:

$${\rm Tr}[ABCD]= {\rm Tr}[BCDA]$$

Así, debido al signo menos en (1), y al hecho de que ${\rm Tr}[\Lambda^2+\Sigma^2]$ es una cantidad fija, el mínimo en (1) se alcanza efectivamente para una matriz ortogonal $O$ tal que

$${\rm Tr}(O^{\rm T}\Lambda O \Sigma) \ \ \text{is maximal}$$

Así se establece la equivalencia entre (*) y nuestro problema inicial.

Answer 3

Parece que la respuesta dada por el usuario1551 es la más adecuada. El enfoque utilizando el cálculo está en detalle en su respuesta. Pero otro enfoque usando el teorema de Birkhoff sugerido en sus comentarios es aproximado. He leído la respuesta enlazada dada por él y trato de dar un resumen informal aquí para ayudar a los interesados.

Matriz estocástica doble y teorema de Birkhoff-von Neumann

La matriz estocástica doble es una matriz cuadrada $A=(a_{ij})$ de números reales no negativos, cada una de cuyas filas y columnas suma 1, es decir $$\sum _{i}a_{ij}=\sum _{j}a_{ij}=1.$$ El teorema de Birkhoff-von Neumann establece que si $A$ es una matriz doblemente estocástica, entonces existe $\theta _{1},\ldots ,\theta _{k}\in (0,1)$ y $\theta _{1} + \ldots + \theta _{k} = 1$ y matrices de permutación $P_{1},\ldots ,P_{k}$ tal que $$A=\theta _{1}P_{1}+\cdots +\theta _{k}P_{k}.$$

La prueba del teorema de Birkhoff-von Neumann se puede encontrar aquí . Aplica el teorema del matrimonio de Hall en la teoría de los gráficos. La prueba del teorema del matrimonio de Hall se puede encontrar aquí . Nunca había aprendido teoría de grafos, pero me parece que la prueba que se ofrece en el enlace no es difícil de seguir si se ha aprendido álgebra lineal. Además, la prueba es muy inspiradora e ingeniosa.

Demostración del enunciado mediante el teorema de Birkhoff-von Neumann

Si $OO^{\rm T} = I$ definimos $Q \equiv (q_{ij}) = (o_{ij})^2$ . Es fácil encontrar que $Q$ es una matriz estocástica doble. Dado que $${\rm Tr}(O^{\rm T}\Lambda O\Sigma) = \sum_{i,j}\lambda_i \sigma_j (o_{ij})^2 = \sum_{i,j}\lambda_i \sigma_j q_{ij},$$ tenemos $$\max_{OO^{\rm T} = I}{\rm Tr}(O^{\rm T}\Lambda O\Sigma) \leq \max_{A} \sum_{i,j}^n\lambda_i \sigma_j a_{ij}, A \mbox{ is double stochastic} .$$

A la luz del teorema de Birkhoff-von Neumann, tenemos $$A=\sum_{l=1}^{k}\theta_l P_{l},$$ donde $\theta _{1},\ldots ,\theta _{k}\in (0,1)$ y $\theta _{1} + \ldots + \theta _{k} = 1$ . Así que tenemos $$\sum_{i,j}\lambda_i \sigma_j a_{ij} = \sum_{l=1}^{k} \theta_{l} \sum_{i,j}\lambda_i \sigma_j p_{ij} .$$ Entre todos $n!$ matrices de permutación, es fácil comprobar $\sum_{i,j}\lambda_i \sigma_j p_{ij}$ tiene un valor máximo $\sum_{i}\lambda_i \sigma_i$ cuando $p_{ij} = \delta_{ij}$ . Así que tenemos $$\max_{A} \sum_{i,j}\lambda_i \sigma_j a_{ij} = \sum_{i}\lambda_i \sigma_i.$$ Por otro lado, tenemos ${\rm Tr}(O^{\rm T}\Lambda O\Sigma) = \sum_{i}\lambda_i \sigma_i$ cuando $O = I$ por lo que podemos concluir que $$\max_{OO^{\rm T} = I}{\rm Tr}(O^{\rm T}\Lambda O\Sigma) = \sum_{i}\lambda_i \sigma_i.$$

Muchas gracias a usuario 1551 ¡por mostrarme estos nuevos y emocionantes conocimientos!