<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN">

<html><body style='font-size: 10pt; font-family: Verdana,Geneva,sans-serif'>

<p>On 09/08/2015 13:29, Matan Ziv-Av wrote:</p>

<blockquote type="cite" style="padding-left:5px; border-left:#1010ff 2px solid; margin-left:5px">

<pre>On Sun, 9 Aug 2015, Oleg Goldshmidt wrote:</pre>

<blockquote type="cite" style="padding-left:5px; border-left:#1010ff 2px solid; margin-left:5px">Shachar Shemesh <<a href="mailto:shachar@shemesh.biz">shachar@shemesh.biz</a>> writes:

<blockquote type="cite" style="padding-left:5px; border-left:#1010ff 2px solid; margin-left:5px">Hi all, I'm looking for a tool/code to invert a matrix. So far, this sounds trivial. I have one special requirement. I did not think it was too special, except I could not find anywhere that supplied it. I want the matrix to be over a different field (i.e. - not the real numbers). In my particular case, I want it to be over Z2 (zero and one).</blockquote>

If you don't find ready code writing your own should be pretty simple for Z2 - fields don't get any simpler. ;-) In general, if you have a matrix A, then its inverse is given by A^(-1) = adj(A)/det(A) [1] The determinant of any matrix over Z2 is either 0 or 1. If it is 0 the matrix is not invertible. If it is 1, then the inverse matrix is the same as the adjugate of the original matrix. Now, the adjugate is the transpose of the cofactor matrix, which is C_ij = (-1)^(i+j)*M_ij [2] where M_ij is A's (ij)-minor, i.e., the determinant of the matrix derived by deleting the i-th row and the j-th column of A. Thus adj(A) = C_ji = (-1)^(i+j)*M_ji [3] Thus, from equations 1 and 3 we have {A^(-1)}_ij = (-1)^(i+j)*M_ji [4] There are probably library routines to compute minors and cofactors. If you don't find any, then, given that all you have is zeroes and ones, it should be easy and safe to write your own. Note that you need to compute the determinant to determine whether or not your matrix is invertible, and to compute the determinant you need the cofactors, since det(A) = Sum_{i=1}^{n} (A_ij*C_ij) [5] So, compute det(A), keep the cofactors, transpose (Eq. [3]) - done. Use</blockquote>

<pre>The last line is wrong. The previous are mathematically correct, but computationally wrong.

When we compute det(A) using [5], we only calculate the minors for the first line, so we only know the minors for the first line, we still need to calculate them for the rest of the lines.

The calculation as suggested above will run in O(n!) steps, this will obviously stop working for matrices of size 15x15 or there about.<br /><br /></pre>

</blockquote>

<p>I should point out that the <strong>simplified</strong> matrix I was using to prove to myself that the idea has merit is 20x20 (inversed using state of the art in the vi text editing front). The code I'll actually have to run will be 273x273. The Matrix itself is sparsish, so it's really not <em>that</em> bad. Still, to prove things are working I'll have to (probably pre-calculate) several thousand such matrices.</p>

<p>In fact, one of my problems in using tools such as Mathematica and friends is that I don't want to hand code the Matrix to be inversed.</p>

<p>Shachar</p>

<div> </div>

</body></html>