2
$\begingroup$

Sincerely I've zero knowledge of this kind of math, but I've recently come to work in a friend's project to calculate a matrix of this size. This friend of mine has tried to do this with excel, with php, with Ruby and now he wants to try Fortran, I just want to know if this is possible with some kind of math-software.

I've read some papers and there are methods to calculate a big matrix of $10\times10$ but no method for a bigger one, this is the origin of my question.

EDIT: this is a sample of the matrix (Excel File): matrix.xlsx

$\endgroup$
9
  • $\begingroup$ Is the matrix sparse (does it have a lot of 0s?) or otherwise nice? $\endgroup$ Jul 23 '14 at 3:55
  • $\begingroup$ Hmm, take R. It is free. And it can deal with relatively big matrices. $\endgroup$ Jul 23 '14 at 3:56
  • $\begingroup$ There exist algorithms with $\mathcal{O}(n^{2.373})$ time complexity, where $n$ is the number of rows/columns. Thus, it should be fine to compute that determinant. $\endgroup$
    – apnorton
    Jul 23 '14 at 3:57
  • $\begingroup$ @EricTressler I've just add a link to download a sample data, this is one of the matrices to calculate ;) $\endgroup$ Jul 23 '14 at 3:57
  • 1
    $\begingroup$ In answer to @EricTressler (so people don't have to necessarily click through to see what type of matrix it is): It is very sparse. $\endgroup$
    – apnorton
    Jul 23 '14 at 3:58
3
$\begingroup$

(This was meant as a comment, not an answer, but it's too long to fit as a comment.)

You asked "Wouldn't that change the result of the operation?", and my reply follows.

No, you can always expand a determinant along any row or column and write it in terms of smaller determinants. It will yield the same result regardless of the row or column you pick. Here's a simple example with a much smaller $3\times 3$ matrix, but the idea is exactly the same. If I pick, say, the first row, which contains entries $a$, $b$, and $c$, I can write the determinant as $$\left| \begin{array}{ccc} a & b & c \\ d & e & f \\ g & h & i \\ \end{array} \right| = a\left| \begin{array}{cc} e & f \\ h & i \\ \end{array} \right| - b\left| \begin{array}{cc} d & f \\ g & i \\ \end{array} \right| +c\left| \begin{array}{cc} d & e \\ g & h \\ \end{array} \right|$$

See how the result is in terms of three smaller determinants? Now, suppose for example that I knew that $a$ and $b$ were both $0$; then I wouldn't need to compute the first two smaller determinants since they are then multiplied by $0$ and so they vanish. In that case, I would be left with a much simpler reduction like this:

$$\left| \begin{array}{ccc} a & b & c \\ d & e & f \\ g & h & i \\ \end{array} \right| = c\left| \begin{array}{cc} d & e \\ g & h \\ \end{array} \right|$$

So a judicious choice of row or column for expansion will let you compute the determinant with very little actual number crunching, if the matrix has a whole lot of $0$ entries. Always look for rows or columns that have as many $0$ entries as possible.

Note the method for expansion: for each entry in the row you choose, form the reduced matrix obtained by omitting the entire row and the entire column containing the entry, multiply the entry by that smaller determinant, stick on an alternating sign, and sum (notice the sign changes I made in using the multipliers: $+a,-b,+c$; same thing works for any size determinant).

$\endgroup$
2
  • 1
    $\begingroup$ You'll gave to be very careful here to exploit the sparsity of the matrix. If done blindly, Laplace expansion will need $168!$ operations, which will take longer than the universe has existed. $\endgroup$
    – lhf
    Jul 23 '14 at 12:07
  • 1
    $\begingroup$ Yes, thus my comment that "a judicious choice of row or column for expansion will let you compute the determinant with very little actual number crunching". $\endgroup$
    – MPW
    Jul 23 '14 at 12:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.