La matrice "tutti uno"!

[j18eos]

Sia
\[
\forall n\in\mathbb{N}_{\geq2},\,J_n=\begin{pmatrix}
1 & 1 & \dotsc & 1\\
1 & \ddots & \ddots & 1\\
\vdots & \ddots & \ddots & \vdots\\
1 & 1 & \dotsc & 1
\end{pmatrix}\in\mathbb{R}^n_n.
\]
Determinare gli autovalori di \(\displaystyle J_n\), i relativi autospazi, dimensioni e basi di questi ultimi, e la matrice diagonalizzante.

Commento: non mi aspetto che questo esercizio resti insoluto a lungo.

[megas_archon]

Il polinomio caratteristico è \(p_{J_n}(t)=(-1)^nt^{n-1}(t-n)\), da cui gli autovalori sono $0$ (con molteplicità $n-1$, che è anche la dimensione del nucleo) e $n$ (con molteplicità 1), sicché non appena scegli una base del nucleo (per esempio \(e_1-e_{i},i=2,\dots,n\)), questa si completa a una base prendendo \(\sum_{k=1}^n e_k\), che è evidentemente un autovettore che genera l'autospazio di $n$.

[080e73990d22b9e30ee6fddddc45a902d78283e6]

Una variante "algoritmica" di questo. Supponiamo di avere una matrice \( M \in \mathbb{M}_n (\mathbb{C}) \) ed una matrice \( \widehat{M} \) ottenuta da \( M\) permutandone ciclicamente colonne e righe; possiamo scrivere cosi' \[ \widehat{M} = \mathcal{P}(M; \bar{m}, \bar{n}) \] dove \( \mathcal{P} \) indica appunto questo tipo di permutazione, \(\bar{m}\) il numero di "shift" verticali e \(\bar{n}\) quelli orizzontali.

Come trovare \(\bar{m}\) e \(\bar{n}\) senza brute force?

[hydro1]

Carino!

\(\widehat{M}=P_1MP_2\), dove $P_1,P_2$ sono delle matrici di permutazione costruite dalla matrice identità shiftando le colonne destra $i_1$ e $i_2$ posizioni. Ora l'idea è che so quali sono gli autovettori di $P_2$: sono gli $n$ vettori della forma $v_1=(1,\zeta_n,\ldots,\zeta_n^{n-1}),v_2=(1,\zeta_n^2,\ldots,\zeta_n^{2(n-1)}),v_3=(1,\zeta_n^3,\ldots,\zeta_n^{3(n-1)}),\ldots$ e i corrispondenti autovalori sono le $n$ radici dell'unità, in un qualche ordine. Ovviamente sapere l'ordine corrisponde a sapere $P_2$. Inoltre i $v_i$ sono una base di $\mathbb C^n$ perchè vivono in autospazi diversi. Ora calcolo gli $Mv_i$, trovando $n$ vettori $w_1,\ldots,w_n$ e gli \(\widehat{M}v_i\), trovando \(\widehat{w}_1,\ldots,\widehat{w}_n\). Il secondo pezzo dell'idea è che moltiplicare a sinistra per $P_1$ ha l'unico effetto di permutare le componenti, e quindi ogni \(\widehat{w}_i\) è ottenuto da un qualche \(\widehat{w}_j\) moltiplicando per una radice dell'unità e shiftando le entrate di $i_1$ posti. Ma chiaramente l'insieme dei \(\widehat{w}_j\) è una base; trovata la matrice del cambio di base, trovate $P_1$ e $P_2$!

[080e73990d22b9e30ee6fddddc45a902d78283e6]

@hydro: esatto. Mi e' venuto in mente quello che cercavo di fare, ovvero trovare \[ \arg \max \, \sum_{i, j} ( \mathcal{P}(M; m, n) \odot \widehat{M})_{ij}, \] con \( \odot \) moltiplicazione di Hadamard. Che dovrebbe essere appunto \( (\bar{m}, \bar{n}) \) per disuguaglianza di riarrangiamento. Tutte quelle radici unitarie e moltiplicazioni tra matrici possono essere scritte come trasformate discrete di Fourier 2D (barando, interpretando matrici come se fossere "immagini") e quindi poi uno puo' usare FFT.