Overleg:Permanent (wiskunde)

Definitie

Ik denk dat het tweede deel van de definitie, laat ik voorlopig zeggen, niet compleet is. Madyno (overleg) 9 okt 2018 20:30 (CEST)

Glynn

Glynn berekent voor iedere $\delta$ en $j$ een som:

$a_{1j}+\delta _{2}a_{2j}+\delta _{3}a_{3j}+\ldots +\delta _{n}a_{nj}$

en vormt het product over $j$. Dat levert als resterende termen op een factor $2^{n-1}$ na

$a_{11}a_{22}a_{33}\ldots a_{nn}$

$a_{11}a_{32}a_{23}\ldots$

etc. Dwz uit de eerste som een element met als tweede index 1, uit de tweede som een element met als tweede index 2, dus eigenlijk de permanent van de getransponeerde. Madyno (overleg) 14 apr 2020 13:41 (CEST)

Madyno, wat is de bedoeling van deze exercitie? Is een overlegpagina een veredeld soort kladpapier? Jaapspies (overleg) 13 apr 2020 23:29 (CEST)

Ik wil proberen op een eenvoudige manier duidelijk te maken wat het verschil is tussen jouw formule en die van Glynn, die in principe hetzelfde zijn. Madyno (overleg) 14 apr 2020 10:05 (CEST)

Het lijkt me geen goed idee om dat op deze plek te doen. Het zicht op de geschiedenis wordt zo verstoord. Wat bijvoorbeeld te denken

van mijn reactie onder het volgende kopje Reactie van Spies?

Ik stel voor dat je de oorspronkelijke pagina terugzet en je uitleg plaatst op een toepasselijke plaats, bijvoorbeeld na die van mij hier onderaan.

Of onder een nieuw kopje. Jaapspies (overleg) 14 apr 2020 21:45 (CEST)

Ik dacht dat je zoiets wel wist, dit hier is alleen maar een voorzet, een uitproberen. Ik denk, en misschien wist jij dat al, dat Glynn eigenlijk de permanent van de getransformeerde berekent. En, voor het reële geval, met jouw argumentatie. Denk je dat hij jouw artikel uit 2006 kent? Madyno (overleg) 15 apr 2020 09:50 (CEST)

Voor ik hier op reageer, graag even aandacht voor het volgende: wat zijn erkende bronnen? Zie verderop. Jaapspies (overleg) 23 apr 2020 10:56 (CEST)

Reactie van Spies

De kwestie is niet een 'eigen' of betere formule. Eigen is onomstreden of zou dat moeten zijn. Spies heeft in 2003 een formule gevonden die eerst in kleine kring is gepubliceerd en in 2006 als 'sidenote' in een artikel in het Nieuw Archief voor Wiskunde (zie literatuurverwijzingen). In een recent artikel wordt de formule in perspectief geplaatst.

Beter in welk opzicht? Notatie? Implementatie in gangbare programmeertalen? Vormgeving?

David Glynn heeft het in een artikel uit 2013 over: "The formula generalizes to infinitely many others". De formule van Spies en de formule van Glynn zijn vrijwel identiek. De afleiding verschilt enorm. De formule van Spies wordt afgeleid met elementaire middelen, terwijl Glynn gebruik maakt van 'invariant theory via the polarization identity for a symmetric tensor'.

Mijn afleiding staat in de afdeling 'Definitie' (beetje vreemd): We zoeken de coefficient van een zekere term in een veelterm. Die redenering is goed te volgen ook voor niet-wiskundigen. De wiskunde die gebruikt wordt is van het niveau VO: Quantoren en gebonden variabelen, $(-1)^{2}=1^{2}=1$ en $t+(-t)=0$. Het stukje eindigt in de formule van Spies:

$per(A)={\frac {1}{2^{n-1}}}\cdot \sum _{x_{1}=1,x_{j}=\pm 1,j>1}(\prod _{i=1}^{n}x_{i})\prod _{i=1}^{n}\sum _{j=1}^{n}a_{ij}x_{j}$

Zoals ook gepubliceerd in het NAW.

Eigenlijk is het treffend hoe ongemerkt met een beetje algebra een "moeilijke" formule wordt afgeleid. Een formule op zich zegt niet zoveel. Het is ook de reis er naar toe die er toe doet. Dat is misschien wel het grootste verschil.

Volgens mij zijn de formules niet 'vrijwel' identiek, maar gewoon hetzelfde. Dat de afleiding volgens Spies in de definitie staat is inderdaad vreemd. Dat moet veranderen. Bovendien moet duidelijk zijn wat van wie is. Madyno (overleg) 22 mrt 2020 14:48 (CET)

De meest elegante oplossing zou zijn na de Definitie een nieuwe kop == Formule van Spies == met daarin de afleiding.

De formules zijn alleen hetzelfde in de zin van 'er komt hetzelfde uit'. Zie ook de opmerking van Glynn.

Dat begrijp ik niet, ik laat toch boven zien dat ze precies hetzelfde zijn?

Madyno (overleg) 22 mrt 2020 15:32 (CET)

Dat kan ik uitleggen. Daar 'boven' wordt gemanipuleerd met gebonden variabelen. Een formule verandert niet essentieel als er een gebonden variabele wordt vervangen. Er bestaat dus een een-eenduidige transformatie van de ene formule in de andere. Gelukkig maar! Dat betekent dat de formules in zekere zin equivalent zijn. Een een-eenduidige transformatie is niet noodzakelijk een identiteit! Glynn heeft het over een equivalentieklasse, een familie van formules. De formules van Spies en de formule van Glynn zijn daar representanten van.

Een formule krijgt betekenis in zijn context. Toeval wil dat de context van de formule van Spies aanwezig is op de actuale wikipediapagina. Mijn voorstel tot introductie van een nieuwe kop ==Formule van Spies== zou dat in een klap duidelijk maken. Het afleiding is helder en leidt tot de formule van Spies. Misschien moeten we dat maar eens proberen.

De formule van Glynn mist context. Dat blijkt onder andere uit de notatie. Er is hier sprake van kolomsommen. Een gevolg van de links-vermenigvuldiging die in bepaalde kringen gebruikelijk is. In Nederland gebruiken we meestal bij matrixvermenigvuldiging de rechts-vermenigvuldiging $y=Ax$. Dat heeft bijvoorbeeld consequenties voor de implimentatie in een gangbare programmeertaal. Een matrix wordt gerepresenteerd door een rij van rijtjes. Een rijsom is dus eenvoudig uit te rekenen. Een kolomsom is wat lastiger. Bij transponeren floept de formule van Glynn ineens in de gedaante van de formule van Spies.

In het aangehaalde artikel uit 2006 in het NAW staat volgens mij alleen:

$\mathrm {per} (A)=2^{-n}\cdot \sum _{x_{i}=\pm 1}Q(x_{1},x_{2},\ldots ,x_{n})$

Madyno (overleg) 23 mrt 2020 00:10 (CET)

Ja, wat wil dat zeggen? Dezelfde formule staat ook op de wikipediapagina. Ik wijs nog maar een keer op mijn artikel in het meest recente nummer van maart 2020 van het NAW. Als print beschikbaar op mijn website.

Sorry, maar ik begrijp er niks van. Laat mij maar zien waarin de formules veschillen! En wat mijn andere opmerking betreft: in de NAW-publicatie wordt jouw formule niet genoemd. Ik wil graag met je meedenken, maar dan moet je wel precies blijven. Madyno (overleg) 23 mrt 2020 15:29 (CET)

Wat ik niet begrijp is het fanatisme waarmee Madyno probeert aan te tonen dat verschillende formules 'hetzelfde' zijn. En ook niet het verwijt dat ik niet precies zou zijn. Ik ben oud (75), maar nog niet seniel of warrig. Een groot deel van mijn werkzame leven ben ik docent Wiskunde en Informatica geweest in verschillende zettingen. Een leerling of student die komt met de mededeling: "ik snap er helemaal niks van", vraag ik terug te komen met een concrete vraag.

Ik zal proberen een en ander nog eens anders uit te leggen. Wat ik hier mis als wiskundige is een schoolbord of moderner een whiteboard. Ideetje voor een toekomstige overlegpagina?

Hoe plaats je eigenlijk zo'n handtekening?

Handtekening: afsluiten met 4 keer ~

Fanatisme? Ik zeg al dat ik graag met je mee denk, maar in mijn optiek ben jij nogal fantiek bezig twee gelijke formules als verschillend op te vatten. Ik ga er niet vanuit dat je seniel of zo bent, maar laat dan maar zien waar ik de fout inga, als ik laat zien dat beide formules hetzelfde zijn.

Madyno (overleg) 24 mrt 2020 12:36 (CET)

Dat ik hier nu ben, heeft ook te maken met een verwijdering met als toelichting "Is hetzelfde, of zoiets", voorbijgaand aan de context van de afleiding. Goed, je vraagt erom. Hier een z.g. whiteboard bestand

Gelukkig komt er wel hetzelfde uit :-)

Jaapspies (overleg) 24 mrt 2020 20:35 (CET) −

Ik had niet ver genoeg gelezen in NAW. Jij geeft wel daar de afleiding van de formule van 'Spies'. Madyno (overleg) 24 mrt 2020 21:23 (CET)

Heb je presentatie bekeken, meester Jaap. Kan ik het zo samenvatten dat de formule van Glynn hetzelfde is als jouw formule toegepast op de getransponeerde? Madyno (overleg) 24 mrt 2020 21:29 (CET)

Niet helemaal. Een formule verandert niet door wat je er invult! Bij transpositie van een matrix wordt een rij een kolom en omgekeerd. De formule van Glynn blijft vanzelfsprekend werken met kolomsommen, maar de invulling lijkt dan op de uitwerking van die andere formule. Probeer maar voor het geval $n=2$.

Wat ik hierboven al schreef: wij zijn in Nederland gewend om te werken met rechtsvermenigvuldiging, daarom ziet de formule van Glynn er in onze ogen vreemd uit. Bij linksvermenigvuldiging van matrices krijg je $y=xA$, waarbij x en y rij-vectoren zijn en zie je bijvoorbeeld $y_{k}=\sum _{i=1}^{n}x_{i}a_{ik}$.

In het stukje 'Definitie' wordt bij de definitie van veelterm $P$ de gewone vermenigvuling gebruikt. Die formulering was voor mij het perfecte haakje om mijn afleiding aan op te hangen. Daar begon ik 2003 met het idee om $P(x_{1},x_{2},\ldots ,x_{n})$ te vermenigvuldgen met $x_{1}x_{2}\ldots x_{n}$, enzovoort.

Dat brengt mij op meedenken. Denk eens even over mijn hierboven gedane suggestie: maak een nieuwe kop == Formule van Spies == direct na de definitie of direct na de introductie van $P$. Er zijn dan nog maar een paar kleine redactionele ingrepen nodig.

Jaapspies (overleg) 25 mrt 2020 12:08 (CET)

Vergelijking

Ik ga niet verder op de links- rechtsvermenigvuldiging in. Dat lijkt me niet relevant. Simpelweg:

Matrix $A=(a_{rk})$, $a_{rk}$ is element in rij $r$ en kolom $k$.

Spies:

$\mathrm {per} _{\text{S}}(A)={\frac {1}{2^{n-1}}}\cdot \sum _{x_{1}=1,x_{j}=\pm 1,j>1}(\prod _{i=1}^{n}x_{i})\prod _{i=1}^{n}\sum _{j=1}^{n}a_{ij}x_{j}$

$\mathrm {per} _{\text{S}}(A^{T})={\frac {1}{2^{n-1}}}\cdot \sum _{x_{1}=1,x_{j}=\pm 1,j>1}(\prod _{i=1}^{n}x_{i})\prod _{i=1}^{n}\sum _{j=1}^{n}a_{ji}x_{j}$

Glynn:

${\rm {per}}_{\text{G}}(A)={\frac {1}{2^{n-1}}}\sum _{x}\left(\prod _{k=1}^{n}x_{k}\right)\prod _{i=1}^{n}\sum _{j=1}^{n}x_{j}a_{ji}$

Conclusie:

${\rm {per}}_{\text{G}}(A)=\mathrm {per} _{\text{S}}(A^{T})$

Maar als formule zijn ze dezelfde. Madyno (overleg) 25 mrt 2020 14:19 (CET)

Mooie, maar ingewikkelde manier om te zeggen dat $A$ en $A^{T}$ dezelfde permanent hebben!

Zoals ik op het "whiteboard" heb uitgelegd hebben we te maken met twee verschillende formules. De ene leeft in de wereld van de linksvermenigvuldiging met rijvectoren en kolomsommen. De ander werkt met kolomvectoren en rijsommen.

Vullen we een concrete matrix in, dan komen we in de uitwerking en spreken we niet meer van een formule, maar van een berekening.

Bovenstaand verhaal vertelt iets over de uitwerking. In de ene formule vul je $A$ in en in de andere $A^{T}$.

Die uitwerkingen lijken op een paar kleinigheden na erg op elkaar. Logisch, want bij transponeren wordt een rij een kolom en omgekeerd.

Jaapspies (overleg) 26 mrt 2020 12:59 (CET)

Dat is toch anders. Omdat $A$ en $A^{T}$ dezelfde permanent hebben, geven beide formules de zelfde, goede uitkomst. Daarbij kan ik jouw afleiding volgen, maar hoe die van Glynn totstandkomt weet ik niet. Wel blijft het een simpel feit dat beide, als formule, hetzelfde zijn. Misschien moet ik voor alle duidelijkheid zeggen: In essentie hetzelfde. Madyno (overleg) 26 mrt 2020 17:52 (CET)

Even voor de duidelijkheid en terzijde. Je noemt me ergens hierboven "meester Jaap". Dat mag, mits goedmoedig bedoeld. Ik ben ooit, lang geleden, afgestudeerd in de zuivere wiskunde en de wijsbegeerte van de wiskunde. Juist die Grondslagen hebben altijd mijn belangstelling gehouden. Verder heb ik in mijn loopbaan aardig wat geprogrammeerd. Zo heb ik bijvoorbeeld het algoritme van Ryser en andere permanent-gerelateerde functies geimplementeerd in sagemath, een open source software pakket om wiskunde te doen. http://www.sagemath.org/

Lees nog even terug wat ik in het begin schreef: "De formule van Spies en de formule van Glynn zijn vrijwel identiek". Lees ook de laatste paragraaf van mijn recente artikel: "It is easy to see that formula (4) is essentially the same as Glynn's".

De formule van Glynn: "... finds a formula by placing the permanent in the context of 'the polarization identity for symmetric tensors', using a different approach to polynomials." Het artikel van Glynn is natuurlijk via elke universiteitsbibliotheek te krijgen. Ik kan je ook een kopie per e-mail sturen.

Misschien wordt het dan nu tijd om te gaan nadenken over hoe we de wikipediapagina beter kunnen maken. Jaapspies (overleg) 27 mrt 2020 10:22 (CET)

Ben je voorlopig tevreden over mijn toevoegingen? Madyno (overleg) 27 mrt 2020 11:09 (CET)

Sorry voor de verlate reactie. Ik was even bezig met andere, ook belangrijke zaken. Mijn complimenten! Ik vind dat je een elegante aanpassing hebt gedaan.

Wat ik nog mis is een verwijzing naar het voor mij belangrijke jaar 2003, het jaar waarin ik het algoritme ontdekte.

Tekstsuggestie: een formule die reeds in 2003 is ontdekt en eerder in 2006 zijdelings door hem vermeld werd in een eerder artikel in het NAW ...

Ik laat het graag aan jou over. Jaapspies (overleg) 28 mrt 2020 10:11 (CET)

Dat zal niet gaan, omdat daar geen erkende bron voor is. Daarom heb ik die verwijzing weggelaten. Het gaat hier ook niet om jou, maar om het begrip 'permanent'. Madyno (overleg) 28 mrt 2020 11:11 (CET)

Wat zijn erkende bronnen? Ik begrijp dat ik niet kan verwijzen naar berichten uit 2003 van Brualdi, Codenotti, Cresta, Sloane, Edwin Clarke en

de American Mathematical Monthly. Wat ik wel gevonden heb in de annalen van de Wikipedia is de vermelding in een tijdschrift dat als betrouwbare

bron bekend staat. In het Nieuw Archief voor Wiskunde staat bij mijn artikel http://www.jaapspies.nl/naw5-2020-21-1-027.pdf een 'lead':

"In January 2003, Jaap Spies found a solution to 'Problem 29' of the old NAW Problem Section. The solution was the permanent of a square matrix. Moments later, he discovered an algorithm for the calculation of the permanent with basic algebraic means. "

Dat lijkt me betrouwbaar genoeg.

Tekstsuggestie: een formule die reeds in 2003 is ontdekt en eerder in 2006 in een terzijde door hem afgeleid werd in een eerder artikel in het NAW ...

Eens? Jaapspies (overleg) 23 apr 2020 10:56 (CEST)

Spies naast Glynn

@Jaapspies: Ik heb het artikel van Glynn gelezen en daarin gebruikt Glynn voor een vierkante matrix dezelfde redenering als jij. Ik moet het nog verder analyseren, maar het is merkwaardig dat Glynn met dezelfde (?) formule de permanent van de gertrtansponeerde uitrekent. Madyno (overleg) 8 apr 2020 11:30 (CEST)

Verschillende afleidingen leiden tot verschillende formules, die weliswaar op elkaar kunnen lijken.

Zie daarvoor bijvoorbeeld mijn artikel in het NAW: http://www.jaapspies.nl/naw5-2020-21-1-027.pdf

Wat je beweert over dezelfde redenering moet ik tegenspreken. De afleidingen verschillen, de formules verschillen.

Nogmaals naast elkaar.

Spies:

Hier is sprake van homogene veelterm $P$ van de orde n in de variabelen $x_{1},x_{2},...x_{n}$. De permanent is

de coefficient van de term die $x_{1}x_{2}\cdots x_{n}$ bevat. Die coefficient kunnen we berekenen met een truc die ik 2003 heb gevonden.

Bij de afleiding is er sprake van een product van rijsommen.

Glynn:

Glynn spreekt over monomials (eentermen) $g$ die ontstaan door de $a_{ij}$'s te vermenigvuldigen, uit elke kolom een.

De variabelen zijn hier de $a_{ij}$'s. Er is hier sprake van een product van kolomsommen.

Die producten dragen natuurlijk alleen bij aan de permanent als ze een 'diagonaalproduct' zijn. De truc is om de coefficienten $c$ van die

monomials te vinden. Nou ja, er staat wat er staat en dat lijkt niet op mijn redenering.

Als je wilt begrijpen wat 'the polarization identity for symmetric tensors' is, moet je in de theorie van Tensoren duiken. Mijn hobby is dat niet,

gezien mijn achtergrond in de zuivere wiskunde en de grondslagen.

Het verschil in notatie en in benadering (links- versus rechtsvermenigvuldiging) heeft met die tensor achtergrond te maken.

Jaapspies (overleg) 9 apr 2020 12:29 (CEST)