Řešení soustav lineárních rovnic (Frobenius)

Tomáš Kalvoda, KAM FIT ČVUT, 2019

Příklad 4.5 a)

Vyřešte soustavu $\mathbb{A} x = b$, kde $\mathbb{A} = \begin{pmatrix} 0 & 4 & 1 & 3 & 2 \\ 1 & 1 & 1 & 4 & 1 \\ 3 & 3 & 3 & 1 & 4 \end{pmatrix} \in \mathbb{Z}_5^{3,5} \quad \text{a} \quad b = \begin{pmatrix} 1 \\ 2 \\ 0 \end{pmatrix} \in \mathbb{Z}_5^3.$

A = matrix(GF(5),[
    [0,4,1,3,2],
    [1,1,1,4,1],
    [3,3,3,1,4]
])
show(A)
b = vector(GF(5), [1,2,0])
show(b)

Všechna řešení homogenní soustavy (tj. všechna $x$ splňující $\mathbb{A} x = 0$; tato množina tvoří podprostor).

S0 = A.right_kernel()
S0

Vector space of degree 5 and dimension 2 over Finite Field of size 5
Basis matrix:
[1 2 2 0 0]
[0 0 0 1 1]

Partikulární řešení nehomogenní soustavy (tj. nějaký vektor $x_p$ splňující $\mathbb{A} x = b$).

xp = A.solve_right(b)
xp

(1, 2, 0, 1, 0)

Ověřme, že to co nám Sage vrátil opravdu má požadované vlastnosti.

# Rozšířená matice soustavy a její horní stupňovitý tvar po provedení Gaussovy eliminace
Aext = zero_matrix(3, 6)
Aext[:, 0:5] = A
Aext[:, 5] = b
show(Aext)
show(Aext.echelon_form())

Dle Frobeniovy věty proto vidíme, že naše soustava má řešení. Dále dimenze množiny řešení homogenní soustavy je $5 - 3 = 2$ (alternativně: máme dva vedlejší sloupce). To náme přesně Sage napočetl, zkontrolujme vlastnosti $S_0$:

print("dimenze S0: %i" % S0.dimension())
print("báze S0:")
basis = S0.basis()
show(basis)
print("Test splnění Ax=0:")
show(A * basis[0])
show(A * basis[1])

dimenze S0: 2
báze S0:

Test splnění Ax=0:

Partikulární řešení opravdu soustavu s pravou stranou řeší:

A * xp == b

True

Když vše shrneme, tak tímto způsobem jsem ze Sage získali řešení ve tvaru $S = (1,2,0,1,0) + \big\langle (1,2,2,0,0), (0,0,0,1,1) \big\rangle.$

V cvičebním pdf je jako výsledek uvedeno

$S = (1,2,0,1,0) + \big\langle (3, 1, 1, 0, 0), (0, 0, 0, 1, 1) \big\rangle.$

Partikulární řešení máme stejné. To ovšem není nutné, jde o libovolné řešení nehomogenní soustavy. Tj. kdybychom měli jiný výsledek, tak vždy stačí ověřit, že platí

A * xp == b

True

Takovýto vektor $x_p$ bude dostačující. Co ale řešení homogenní soustavy? Očividně v obou případech jsou dvoudimenzionální, ale jsou stejné? Lineární obal ze cvičení je podprostor:

S0cvika = (GF(5)^5).span([vector([3,1,1,0,0]), vector([0,0,0,1,1])])
S0cvika

Vector space of degree 5 and dimension 2 over Finite Field of size 5
Basis matrix:
[1 2 2 0 0]
[0 0 0 1 1]

V Sage tyto podprostory můžeme snadno porovnat:

S0 == S0cvika

True

Tímto jsme ověřili, že oba výsledky jsou opravdu totožné.