Numero moltiplicazioni per trovare determinante usando la "grande formula"
Ciao a tutti !
Oggi mi rivolgo a voi per chiarire il dubbio che ho espresso nel titolo. Riferendomi alla "grande formula" (non so se abbia anche altri nomi) per il calcolo del determinante, cioè: $det(A)=sum_(P) (a_(1alpha)a_(2beta)...a_(n nu))det(P)$ essendo $(1,...n)$ e $(alpha,...nu)$ rispettivamente le righe e le colonne della matrice A ed essendo P la matrice di permutazione, in un esercizio tratto dallo Strang mi viene chiesto di trovare il numero di moltiplicazioni necessario per calcolare il determinante utilizzando la suddetta formula ed il risultato è il seguente: $(n-1)n! $(ogni termine $n-1)$. Quello che non afferro è l'ultimo pezzo, se sia una parte della soluzione o se sia una puntualizzazione, proprio non mi è chiaro, cioè (ogni termine $n-1)$. Che vuol dire ? Se ho capito bene, gli altri due termini si riferiscono, il primo al numero di moltiplicazioni dei termini della matrice A ed il secondo (n!) al numero delle matrici di permutazione; per fare un esempio, applicando la formula alla matrice $A=[ ( a_11 , a_12 , a_13 ),( a_21 , a_22 , a_23 ),( a_31 , a_32 , a_33 ) ]$ si ottiene $det(A)=a_11a_22a_33| ( 1 , , ),( , 1 , ),( , , 1 ) |+a_12a_23a_31| ( , 1 , ),( , , 1),( 1 , , ) | +a_13a_21a_32| ( , , 1 ),( 1 , , ),( , 1 , ) |+a_11a_23a_32| ( 1 , , ),( , ,1 ),( , 1 , ) |+a_12a_21a_33| ( , 1 , ),( 1 , , ),( , , 1 ) |+a_13a_22a_31| ( , , 1 ),( , 1 , ),( 1 , , ) |$
e dunque le moltiplicazioni mi sembrano $(n-1)$ riferite ai termini $a$, cioè, ad esempio, $a_11a_22a_33$ presenta 2 moltiplicazioni (cioè n-1=2, con n numero righe e colonne della matrice A), il tutto ripetuto per le matrici di permutazione che sono n!. Dunque da dove viene e cosa significa l'ultimo termine ?
Grazie a quanti riusciranno a chiarire il mio dubbio.
Come sempre, saluti
Oggi mi rivolgo a voi per chiarire il dubbio che ho espresso nel titolo. Riferendomi alla "grande formula" (non so se abbia anche altri nomi) per il calcolo del determinante, cioè: $det(A)=sum_(P) (a_(1alpha)a_(2beta)...a_(n nu))det(P)$ essendo $(1,...n)$ e $(alpha,...nu)$ rispettivamente le righe e le colonne della matrice A ed essendo P la matrice di permutazione, in un esercizio tratto dallo Strang mi viene chiesto di trovare il numero di moltiplicazioni necessario per calcolare il determinante utilizzando la suddetta formula ed il risultato è il seguente: $(n-1)n! $(ogni termine $n-1)$. Quello che non afferro è l'ultimo pezzo, se sia una parte della soluzione o se sia una puntualizzazione, proprio non mi è chiaro, cioè (ogni termine $n-1)$. Che vuol dire ? Se ho capito bene, gli altri due termini si riferiscono, il primo al numero di moltiplicazioni dei termini della matrice A ed il secondo (n!) al numero delle matrici di permutazione; per fare un esempio, applicando la formula alla matrice $A=[ ( a_11 , a_12 , a_13 ),( a_21 , a_22 , a_23 ),( a_31 , a_32 , a_33 ) ]$ si ottiene $det(A)=a_11a_22a_33| ( 1 , , ),( , 1 , ),( , , 1 ) |+a_12a_23a_31| ( , 1 , ),( , , 1),( 1 , , ) | +a_13a_21a_32| ( , , 1 ),( 1 , , ),( , 1 , ) |+a_11a_23a_32| ( 1 , , ),( , ,1 ),( , 1 , ) |+a_12a_21a_33| ( , 1 , ),( 1 , , ),( , , 1 ) |+a_13a_22a_31| ( , , 1 ),( , 1 , ),( 1 , , ) |$
e dunque le moltiplicazioni mi sembrano $(n-1)$ riferite ai termini $a$, cioè, ad esempio, $a_11a_22a_33$ presenta 2 moltiplicazioni (cioè n-1=2, con n numero righe e colonne della matrice A), il tutto ripetuto per le matrici di permutazione che sono n!. Dunque da dove viene e cosa significa l'ultimo termine ?
Grazie a quanti riusciranno a chiarire il mio dubbio.
Come sempre, saluti
Risposte
Non mi è chiara la formula che stai cercando di capire.
Allora, ci sono \(n!\) permutazioni. Ignorando le operazioni per calcolare \(\det(P)\), ci sono \(n\) moltiplicazioni per permutazioni (\(n-1\) tra gli elementi della matrice e la moltiplicazione del risultato per \(\det(P)\)). A questo punto non rimane che calcolare il numero di moltiplicazioni \(f(n)\) per calcolare \(\det(P)\) e avrai \(n!(n + f(n))\).
[edit] Avevo scritto una cosa sbagliata prima.
Allora, ci sono \(n!\) permutazioni. Ignorando le operazioni per calcolare \(\det(P)\), ci sono \(n\) moltiplicazioni per permutazioni (\(n-1\) tra gli elementi della matrice e la moltiplicazione del risultato per \(\det(P)\)). A questo punto non rimane che calcolare il numero di moltiplicazioni \(f(n)\) per calcolare \(\det(P)\) e avrai \(n!(n + f(n))\).
[edit] Avevo scritto una cosa sbagliata prima.
Ciao vict85 !
Innanzitutto grazie della risposta. Quello che non riesco a capire è il risultato dell'esercizio che dice che applicando quella formula per trovare il determinante occorrono $(n-1)n!$(ogni termine $n-1$) moltiplicazioni. In particolare non mi è chiaro l'ultimo termine cosa rappresenta. Inoltre per trovare det(P) se non erro non occorrono moltiplicazioni, perché so già che det(P) può essere solo $+-1$ a seconda di quanti scambi di righe devo fare per ottenere $| ( 1 , , ),( , 1 , ),( , , 1 ) |$; scambi pari=+1, scambi dispari=-1; per esempio $| ( , 1 , ),( , , 1 ),( 1 , , ) |=1$. In particolare non mi è chiaro cosa indichi (ogni termine $n-1$) nel risultato.
Innanzitutto grazie della risposta. Quello che non riesco a capire è il risultato dell'esercizio che dice che applicando quella formula per trovare il determinante occorrono $(n-1)n!$(ogni termine $n-1$) moltiplicazioni. In particolare non mi è chiaro l'ultimo termine cosa rappresenta. Inoltre per trovare det(P) se non erro non occorrono moltiplicazioni, perché so già che det(P) può essere solo $+-1$ a seconda di quanti scambi di righe devo fare per ottenere $| ( 1 , , ),( , 1 , ),( , , 1 ) |$; scambi pari=+1, scambi dispari=-1; per esempio $| ( , 1 , ),( , , 1 ),( 1 , , ) |=1$. In particolare non mi è chiaro cosa indichi (ogni termine $n-1$) nel risultato.
Era esattamente quello che non mi era chiaro. Ho effettivamente cercato di dare una risposta un po' troppo da programmatore (è il mio mestiere anche se sono laureato in matematica). Se permutazioni e segni sono determinati a priori, allora la risposta è \(n!(n-1)\). Penso che il libro/il professore volesse solo esplicitare che era \(n!(n-1)\) e non \(\big[(n-1)n\big]! = (n^2-n)!\)
Grazie ancora vict85. Credo di aver capito cosa intendi. Tuttavia il mio dubbio permane ancora, proprio perché se leggo $(n-1)n!$ per me è chiaro che il fattoriale si riferisca solo alla n, altrimenti dovrei scrivere, come te, $((n-1)n)!$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo