Il problema del matching massimo su grafo: un approccio algebrico

Nei prossimi paragrafi lavoreremo, anche, con matrici ad ingressi indeterminati. Presentiamo,
dunque, l'estensione di alcune proprietà fondamentali delle matrici con entrate reali a matrici con entrate indeterminate.

Consideriamo una matrice K con alcune entrate reali ed altre delle variabili indipendenti non nulle. Diremo che Ǩ è una assegnazione di K se è ottenuta rimpiazzando le indeterminate di K con dei valori numerici ([1]).

Dati due vettori u, v dello stesso ordine con entrate indeterminate, diremo che u e v sono linearmente indipendenti se esiste una loro assegnazione ũ e ṽ tale che i due vettori sono linearmente indipendenti. Al contrario, diremo che u e v sono linearmente dipendenti se per ogni assegnazione ũ e ṽ i due vettori sono linearmente dipendenti.

Data una matrice M ad entrate indeterminate possiamo osservare che il determinante di M è un polinomio. Diremo M non singolare o invertibile se il suo determinante è non identicamente nullo.
Con abuso di notazione scriveremo che M è non singolare se e solo se det(M) ≠ 0.
Il rango di M è il massimo numero di righe o colonne linearmente indipendenti di M. Una base per le righe di M è un insieme massimale di righe linearmente indipendenti, mentre una base per le colonne di M è una base per le righe di M^T (i.e la trasposta di M).