Linjära ekvationssystem med heltal

Innan man tänker på kravet att det ska vara med så få operationer som möjligt, kan du någon metod som löser problemet överhuvudtaget (kanske även men irriterande många operationer)?

Tack för återkopplingen! Kan ingen smidig metod direkt (finns troligen inte), men man kan iaf förenkla problemet genom att skriva om det medelst ”Hermite normal form” så att det fås på formen:

$Hy=b$ där $H$ är en diagonalmatris.

Hittade en metod här också, men har inte provat den i praktiken:

http://sites.math.rutgers.edu/~sk1233/courses/ANT-F14/lec3.pdf

Jag blir lite osäker på varför du gör en Hermite-representation om du ändå inte vet vad du ska använda formen till. Vanligtvis går man ju baklänges genom ett problem genom att först utveckla en strategi och sedan lista ut hur delstegen görs. Här är dock mina funderingar: (Sammanfattning i nästa inlägg)

Om man bortser från att det hela gäller heltal en sekund och går tillbaka till linjära algebrans grundprinciper och tänker på problemet geometriskt så urgör var och en av de m ekvationerna ett hyperplan i rummet Rn \mathbb R^n . Dessa hyperplan skär varandraoch skärningen bildar att annat hyperplan.

Hade det varit två linjer hade skärningen kunnat vara en punkt, skärningen mellan två plan en linje, osv. Heltalslösningarna måste också ligga på detta hyperplan så taktiken blir att först bestämma hyperplanets ekvation och därefter extrahera just lösningarna med heltalspunkter.

Låt säga att vi hade haft

2x + 3y + 5z = 1

6x + 18y - 11z = 2

och sedan gör man divisionsfri gausseliminering genom att multiplicera ekvationerna så att koefficienterna längs någon kolumn blir en gemensam multipel

6x + 9y + 15z = 3 (ggr 3) 

6x + 18y - 11z = 2

och efter att ha subtraherat den första med den andra är problemet reducerat till

-9y + 26z = 1

6x + 18y - 11z = 2

där ekvationen med få okända (den första) motsvarar ekvationernas skärningsyta. (Som jag tolkar det är denna process analog med Hermite-representationen)  Om vi löser den  med minst antal okända (den första ekvationen) som en normal linjär diofantiskt ekvation får vi att lösningarna ska vara

y = -3 + 26k (*)

z = -1 - 9k (**)

där k är en hjälpvariabel som än så länge kan variera över alla heltal.

Om vi nu återsubsituerar detta in i den andra ekvationen 6x + 8y - 11z = 2 får vi

6x + 18(-3 + 26k) - 11(-1 - 9k) = 2

6 x + 567k = 45

vilket har lösning

x = -189n - 87

k = 2n + 1

Om vi slutligen substituerar k = 2n + 1 i (*) och (**) får vi 

y = -3 + 26k  = -3 + 26(2n + 1) = 52n + 23

z = -1 - 9k = -1 - 9(2n + 1) =-18 n - 10

så sammanfattningsvis

x = -189n - 87

y = 52n + 23

z = -18 n - 10

där n är ett godtyckligt heltal. Notera att dessa punkter ligger på en linje. 

Jag gör ett nytt inlägg där jag sammanfattar och kommenterar på denna strategi. 

EDIT: Slarv som skapade kedjeproblem. Förmodligen fortfarande slarv i uträkningarna...

Sammanfattning:

1. Utför radoperationer och skriver systemet i något analogt med Hermite-form där varochen av ekvationerna har n, n-1, n-2, ..., n-m + 1 okända. 

2. Löser ekvationen med minst okända (n - m + 1) som en linjär diofantiskt ekvation med valfri metod och får uttryck för n - m + 1 variabler beroende av n - m  heltalsparametrar.

3. Dessa återsubstituerar man i ekvationen ovan för att få en ny ekvation involverande en av de okända och de n - m heltalsparametrarna vilka löses och uttryck fås för dessa beroende av n-m + 1 nya hjälpparametrar. 

4. Upprepa steg 3 ad nauseaum tills dess att alla ursprungliga okända beskrivs av en mängd hjälpparametrar.

(Detta kan vara svårt att följa utan exemplet)

Detta är ett exempel på en av de där lösingsmetoderna som skalas katastrofalt dåligt då att lösa enskilda heltalsekvationer i sig är tidskrävande, men blir alltså en fungerande metod som kan användas som referens för om andra metoder är bättre. 

Stort tack för den grundliga förklaringen och det tydliga exemplet! Ska prova denna metod!

Ska dock poängtera att mitt exempel var snällt i meningen att alla ekvationer man löser har två okända. Om man säg har 3 ekvationer och 6 okända så kan vi landa i att den diofantiska ekvationen vi börjar med har 4 okända såsom

2x + 3y + 5z + 7w = 13 (finn alla heltal x,y,z,w som satisfierar detta)

och att lösa sådana ekvationer är en övning i finess och tålamod. Första gången man löst en sådan är man ju glad men andra gången är man väldigt väldigt ledsen haha. 

EDIT: Jag misstänker att datalogerna hittat något trick för att optimera det hela.

Tycker du ska utforska din ursprungliga idé med "Hermite normal form" för systemet $Ax=b$

Med SeriousCephalopods exempel får vi (i kolonnvariant) AU=H (se wolfram)

$\begin{bmatrix}2&3&5\\6&18&-11\end{bmatrix}\begin{bmatrix}-40&-7&-123\\17&3&52\\6&1&18\end{bmatrix}=\begin{bmatrix} 1&0&0\\0&1&0\end{bmatrix}$

Nu ser vi att delen av H framför 0:an $\hat{H}$ är identitetsmatrisen så 

$z_0=\begin{bmatrix} \hat{H}^{-1}b\\0\end{bmatrix}=\begin{bmatrix} b\\0\end{bmatrix}$

$x_0=Uz_0=\begin{bmatrix}-40&-7&-123\\17&3&52\\6&1&18\end{bmatrix}\begin{bmatrix}1\\2\\0 \end{bmatrix}=\begin{bmatrix}-54\\23\\8 \end{bmatrix}$

Vilket är en partikulärlösning. Den vektor (gcd=1) som spänner nollrummet till A. N(A), är $(123,-52,-18)$ (sista kolonnen i U). Alltså blir den allmänna lösningen:

$\begin{matrix}x&=&-54+123n\\y&=&23-52n\\z&=&8-18n\end{matrix}$

Denna metod kostar polynomisk tid.

Riktigt snyggt Guggle! Tack!