Esercizio carino di algebra lineare

[NightKnight1]

Voglio postare un esercizio curioso di algebra lineare.

Sia $A \in M_(2n,2n)(RR)$ una matrice quadrata reale di ordine pari che ha zeri sulla diagonale e 1 o -1 altrove: $a_{ii}=0 \ , \ a_{ij}= \pm 1$.
Dimostrare che $A$ e' invertibile.

[miuemia]

beh se ha soltanto tutti -1 oppure soltanto tuti +1 la cosa è semplice.... devo pensarci quando ci sono sia +1 che -1.

[adaBTTLS1]

io penso invece che non cambia nulla tra il caso di tutti i termini +1 o -1 e il caso proposto.
sono certa che dipende dal fatto che i termini non nulli del determinante sono in numero dispari, ma dimostrarlo è meno banale del previsto, anche perché
$(2n)! - (2n-1)!$ è un numero pari...

[NightKnight1]

La soluzione che hanno detto a me richiede un intuizione quasi geniale.

Suggerimento:

osservare che $A \in M_{2n,2n}(ZZ)$

[fu^2]

Dopo due giorni l'illuminazione: mi ero infilato in una strada a vicolo cieco pensando ai determinanti, poi sono tornato su considerazioni sul rango e ne sono uscito. Ditemi se vi convince (non è una dimostrazione troppo formale, nei prossimi gg la sistemo, ho dato, se non ho sbagliato, il senso delle cose):

sia $v_i=((\vdots),(+-1),(vdots),(0),(vdots),(+-1),(vdots))$ il vettore che ha zero all $i$-esima componente.Allora $A=[v_1,...,v_{2n}]$.

Da notare che $\|v_i\|^2=2n-1$ per ogni $i$ (qui si usa che la grandezza è pari).

Definiamo $u_1=v_1$.

Se notiamo che $$, $i!=j$ è un numero pari compreso tra $2-2n$ e $2n-2$ essendo che saltano due componenti dovute agli zeri tutti sfasati tra di loro e le altre componenti sono uno o meno uno, quindi si ha che $\=(-)^k+...+(-)^k$ con $k=1,2$ a seconda del segno scelto per la componente. Concludiamo l'osservazione notando che $()/()=M/(2n-1)$ dove $M$ è pari.

Quindi se applichiamo il processo di Gram-smidt risulterà chiaro che non esiste nessuna combinazione di numeri pari che diano un numero dispari, ovvero al passo i-esimo avremo, detto $M_k=$ e $N_k=$ che $u_i=v_i-sum_k M_k/N_ku_k$.

Per vedere che $u_i!=0$ basta notare che $sum_k M_k/N_k!=0,1$ essendo che si ha un pari diviso un dispari.
Questo discende dal fatto che $$ ha numeratore pari e denominatore dispari, mentre $$ ha numeratore dispari in quanto alemeno una componente è dispari essendo che sarà data da un $1-h/q$ con $h$ pari e $q$ dispari.
(si vede facilmente guardando come sono definiti i vettori e le loro norme, se ho tempo nei prossimi giorni riscirvo meglio questa parte lasciata a parole che data l'ora non ho voglia di scrivere per bene ).

Spero di aver messo gli indici tutti al posto giusto e essere stato sufficientemente chiaro.


Il processo di ortogonalizzazione è andato a buon fine quindi $span{u_1,...,u_{2n}}=span{v_1,...,v_{2n}}$ e la prima è una base ortogonale per $RR^{2n}$. Abbiamo mostrato che $A$ ha rango pieno essendo le sue colonne linearmente indipendenti, concludiamoc he $A$ è invertibile.

[e3353cdc139f9576d1418ef5ef3cff2aac614a86]

Salve a tutti!

Propongo una soluzione usando i determinanti.

Procedo per induzione su $n$. Per $n=1$ abbiamo una matrice $2 xx 2$ con zeri sulla diagonale e $pm 1$ altrove, ed è immediato che tale matrice è invertibile. Supponiamo quindi $n>1$. A meno di cambiare segno alle righe e/o alle colonne (la qual cosa ci porta ad una matrice la cui invertibilità è equivalente a quella della matrice di partenza) possiamo supporre che la matrice $A$ sia di questa forma:

$((0,1,1,...,1),(1,0,circ,...,circ),(1,circ,0,...,circ),(vdots,vdots,vdots,ddots,vdots),(1,circ,circ,...,0))$.

Il circoletto $circ$ indica un qualsiasi elemento in ${1,-1}$. Ricordiamo che per ipotesi induttiva la matrice ottenuta eliminando la "cornice" (cioè la prima e l'ultima riga, la prima e l'ultima colonna) è invertibile. Chiamiamo "tela" tale matrice (giusto per pensare ad $A$ come a un quadro ).
Ora l'invertibilità di $A$ è equivalente a quella della matrice che ottengo da questa sostituendo la seconda colonna (riga) alla differenza tra la seconda e la terza colonna (riga), poi alla terza colonna (riga) la differenza tra la terza e la quarta e così via, quindi posso supporre che $A$ sia di questa forma:

$((0,0,0,...,1),(0,*,*,...,*),(0,*,*,*,*),(vdots,vdots,vdots,ddots,vdots),(1,*,*,...,*))$.

Ricordo che la tela di quest'ultima matrice è ottenuta dalla tela della precedente facendo operazioni elementari su righe e colonne, quindi è anch'essa invertibile. Ma allora sviluppando il determinante con laplace usando gli uni nelle posizioni (1,2n) e (2n,1) troviamo che il determinante di $A$ è uguale a meno del segno al determinante della sua tela, e quindi è diverso da zero.

[NightKnight1]

"fu^2":
Quindi se applichiamo il processo di Gram-smidt risulterà chiaro che non esiste nessuna combinazione di numeri pari che diano un numero dispari, ovvero al passo i-esimo avremo, detto $M_k=$ e $N_k=$ che $u_i=v_i-sum_k M_k/N_ku_k$.

Per vedere che $u_i!=0$ basta notare che $sum_k M_k/N_k!=0,1$ essendo che si ha un pari diviso un dispari.
Questo discende dal fatto che $$ ha numeratore pari e denominatore dispari, mentre $$ ha numeratore dispari in quanto alemeno una componente è dispari essendo che sarà data da un $1-h/q$ con $h$ pari e $q$ dispari.
(si vede facilmente guardando come sono definiti i vettori e le loro norme, se ho tempo nei prossimi giorni riscirvo meglio questa parte lasciata a parole che data l'ora non ho voglia di scrivere per bene ). .

per fu^2: Devo riflettere meglio su questo punto (che e' il punto cruciale); lo farò nei prossimi giorni.

La soluzione di Martino mi sembra corretta.

Complimenti!

Comunque la soluzione che hanno detto a me e' molto più corta ed elegante:

Osservo che la matrice $A \in M_{2n}(ZZ)$; considero $B \in M_{2n}(F_2)$ la ridotta di $A$ modulo 2 (dove $F_2$ denota il campo con 2 elementi). Poiche' il determinante e' un polinomio nei coefficienti e la riduzione modulo 2 e' un omomorfismo di anelli si ha che la classe-resto modulo 2 del numero intero $det A \in ZZ$ e' $det B \in F_2$; se mostro che $det B = 1$ avrei che $det A$ e' un numero dispari e quindi non può essere nullo.
Osservo che la matrice $B$ ha tutti 0 sulla diagonale e 1 altrove.
Considero il sistema lineare $Bx=0$ dove $x=((x_1),(vdots),(x_{2n})),0 \in (F_2)^{2n}$; per $1 \leq i < j \leq 2n$ considero la i-esima e la j-esima equazione:
$x_1 + ... +x_{i-1} + x_{i+1} + ... + x_{j-1} + x_j + x_{j+1} + ... + x_{2n} = 0$
$x_1 + ... +x_{i-1} + x_i + x_{i+1} + ... + x_{j-1} + x_{j+1} + ... + x_{2n} = 0$
sommando membro a membro e ricordando che siamo in $F_2$ ottengo:
$x_i + x_j = 0$ ovvero $x_i = x_j$;
questo prova che se il vettore $x$ sta nel nucleo della matrice $B$, allora deve avere tutte le componenti uguali. Ma in $(F_2)^{2n}$ ci sono solo due vettori che hanno questa proprietà: $((0),(vdots),(0)) \ , \ ((1),(vdots),(1))$; ma il secondo vettore non e' soluzione per la parità di 2n.
Quindi abbiamo mostrato che l'unico vettore che sta nel nucleo di $B$ e' il vettore nullo; ciò prova l'invertibilità della matrice $B$.

[e3353cdc139f9576d1418ef5ef3cff2aac614a86]

@NightKnight: accidenti, quindi la soluzione era riflettere abbastanza a lungo sull'idea di adaBTTLS
Bello!

[miuemia]

carino davvero questo esercizio!

[e3353cdc139f9576d1418ef5ef3cff2aac614a86]

Osservo che c'e' anche una interpretazione in termini di dearrangiamenti.
Mettiamoci nel caso in cui $A$ ha $1$ fuori dalla diagonale e $0$ sulla diagonale.

Un dearrangiamento su $n$ oggetti e' una permutazione di $n$ oggetti senza punti fissi. Detto $D[n]$ l'insieme dei dearrangiamenti su $n$ oggetti, si ha allora che $det(A)=sum_{sigma in D[n]}sgn(sigma)$. In questo modo il problema diventa: mostrare che i dearrangiamenti su $2n$ oggetti sono in numero dispari.

Trovare il valore esatto di $|D[n]|$ e' un'altra storia...