Opdracht 4: Het bepalen van de determinant van een matrix met gehele getallen als entries Een methode om de determinant van een n bij n matrix te berekenen is door te vegen: tel een geschikt gekozen aantal maal de eerste rij op bij de tweede zodat de eerste coefficient nul wordt, doe dit voor alle rijen. Ga nu door met de tweede rij en maak de lager gelegen elementen in de tweede rij nul. (Als het tweede element op de hoofddiagonaal nul is kan dit niet, maar dan weten we dat de determinant nul is). Je krijgt uiteindelijk een matrix waarvan de helft onder de hoofddiagonaal uit alleen maar nullen bestaat. De determinant is nu het product van alle elementen op de hoofddiagonaal. Als we dit proces met gehele getallen als elementen doen, treden er in het algemeen rationele getallen met grote tellers en noemers op, zodat de vraag rijst of dit proces wel polynomiaal in de input is. Het antwoord is ja, maar dit te bewijzen is niet triviaal ! Een andere methode is de chinese reststelling toe te passen. Dit is dan ook de opgave: ******** Bepaal de determinant van een matrix met gehele getallen door de chinese reststelling toe te passen. ******** Dan moeten we echter wel een bovengrens voor de grootte van de determinant in termen van de input weten. Gebruik hiervoor |det(A) | <= n^{n/2}*B^n=C, met B een bovengrens voor de absolute waarde van de entries (elementen) van de matrix. Merk op dat det(A) in een interval met hooguit 2*C+1 gehele getallen ligt. Kies nu r=log(2*C+1)/log(2) en rond dit naar boven af. Dan geldt dat p_1*....*p_r >=2^r>=2*C+1, met p_1=2, p_2=3, p_3=5, ... de opeenvolgende priemgetallen. Opmerking: Een efficientere methode is niet om bij p=2 maar bij wat grotere priemgetallen te beginnen, zeg vanaf het 10000e priemgetal (dan heb je een stuk minder priemgetallen nodig), dit laat zich ook gemakkelijk implementeren. Wanneer hun product >=2*C+1 is, dan kun je de determinant uniek bepalen. Bepaal nu de determinant modulo p_i for i=1...r (reduceer de entries mod p, de inverses bij het vegen volgen uit het euclidische algoritme) en bepaal hieruit de determinant zelf. Meer uitleg staat in Sectie 5.5 van het boek: Modulair determinant computation, maar de informatie zoals hier geschetst moet voldoende zijn om het zelf aan te kunnen !