Matrice unimodulară

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 9 noiembrie 2021; verificarea necesită 1 editare .

O matrice unimodulară este o matrice pătrată cu coeficienți întregi , al cărei determinant este sau . Acestea sunt exact acele matrice non- singulare pentru care ecuația are o soluție întreagă pentru orice vector întreg . $+1$ $-unu$ $A$ $ax=b$ $b$

Proprietăți

Matricele unimodulare formează un grup de multiplicare , adică următoarele matrice sunt unimodulare:

Matrice de identitate
Matrice inversă la unimodulară
Produsul a două matrice unimodulare

Matrice complet unimodulară

O matrice dreptunghiulară se numește complet unimodulară (sau absolut sau total unimodulară) dacă toate minorele sale iau valori din mulțime . Cu alte cuvinte, oricare dintre submatricele sale pătrate nedegenerate este unimodulară. $\{-1,0,+1\)$

Matricele complet unimodulare joacă un rol important în teoria programării liniare întregi : problemele de programare liniară cu un sistem de constrângeri de forma , unde este complet unimodulară și este un vector întreg, au soluții fezabile de bază integrale și, prin urmare, în special, poate fi rezolvată printr-un instrument standard de programare liniară - o metodă simplex . $ax = b$ $A$ $b$

Câteva exemple de matrice complet unimodulare:

matricea de incidență a oricărui grafic direcționat ;
matricea de incidență a unui graf bipartit nedirecționat ;
exemplu privat: ${\begin{bmatrix} -1&-1&0&0&0&+1\\+1&0&-1&-1&0&0\\0&+1&+1&0&-1&0\\0&0&0&+1&+1&-1\\\end{bmatrix)).$

Matrice polinomială unimodulară

Teoreme

Teorema 1: O matrice polinomială este unimodulară dacă și numai dacă toți factorii săi invarianți sunt egali cu unul, adică. când este echivalentă cu matricea identitară.

Teorema 2: O matrice polinomială este unimodulară dacă și numai dacă este un produs al elementelor matricei .

Literatură

Berge K. Teoria grafurilor și aplicațiile sale. Capitolul 15. M., IL, 1962.
Papadimitriou H., Steiglitz K. Optimizare combinatorie . Algoritmi și complexitate. 1984.
Emelichev V.A. Poliedre. Contează. Optimizare. Capitolul IV. 1981.