16
\$\begingroup\$

The cofactor matrix is the transpose of the Adjugate Matrix. The elements of this matrix are the cofactors of the original matrix.

The cofactor enter image description here (i.e. the element of the cofactor matrix at row i and column j) is the determinant of the submatrix formed by deleting the ith row and jth column from the original matrix, multiplied by (-1)^(i+j).

For example, for the matrix

enter image description here

The element of the cofactor matrix at row 1 and column 2 is:

enter image description here

You can find info on what the determinant of a matrix is and how to calculate them here.

Challenge

Your goal is to output the cofactor matrix of an input matrix.

Note: Built-ins that evaluate cofactor matrices, or adjugate matrices, or determinants or anything similar are allowed.

Input

The matrix may be inputed as a command line argument, as a function parameter, in STDIN or in any way that is most appropriate for the language you use.

The matrix will be formatted as a list of lists, each sublist corresponding to one row, which contains factors ordered from left to right. Rows are ordered from top to bottom in the list.

For example, the matrix

a b
c d

will be represented by [[a,b],[c,d]].

You may replace the square brackets and commas with something else if it fits your language and is sensible (e.g. ((a;b);(c;d)))

Matrices will only contain integers (which can be negative).

Matrices will always be square (i.e. same number of rows and columns).

You may assume that the input will always be correct (i.e. no formatting problem, nothing other than integers, no empty matrix).

Output

The resulting cofactor matrix may be outputed to STDOUT, returned from a function, written to a file, or anything similar that naturally suits the language you use.

The cofactor matrix must be formatted in the exact same way the input matrices are given, e.g. [[d,-c],[-b,a]]. If you read a string, then you must return/output a string in which the matrix is formatted exactly like in the input. If you use something like e.g. a list of lists as input, then you must return a list of lists too.

Test cases

  • Input: [[1]]

Output: [[1]]

  • Input: [[1,2],[3,4]]

Output: [[4,-3],[-2,1]]

  • Input: [[-3,2,-5],[-1,0,-2],[3,-4,1]]

Output: [[-8,-5,4],[18,12,-6],[-4,-1,2]]

  • Input: [[3,-2,7,5,0],[1,-1,42,12,-10],[7,7,7,7,7],[1,2,3,4,5],[-3,14,-1,5,-9]]

Output:

[[9044,-13580,-9709,23982,-9737],[-1981,1330,3689,-3444,406],[14727,7113,2715,-9792,414],[-28448,-2674,-707,16989,14840],[-2149,2569,-2380,5649,-3689]]

Scoring

This is so the shortest answer in bytes wins.

\$\endgroup\$
  • 2
    \$\begingroup\$ I am not sure how to interpret the cofactor matrix must be formatted in the exact same way the input matrices are given for function submissions that get input from arguments and return a value. Do we read/return actual matrices or their string representations? \$\endgroup\$ – Dennis Dec 16 '15 at 22:51
  • 1
    \$\begingroup\$ In short: if you read a string, then you must return/output a string in which the matrix is formatted exactly like in the input. If you use something like e.g. a list of lists, then you must return a list of lists too. \$\endgroup\$ – Fatalize Dec 17 '15 at 8:15
  • \$\begingroup\$ Does a 1x1 matrix really have a cofactor matrix? \$\endgroup\$ – Liam Dec 18 '15 at 7:11
  • \$\begingroup\$ Also your penultimate test case seems to be the adjugate matrix (the transpose of what it should be), unless I'm mistaken. \$\endgroup\$ – Liam Dec 18 '15 at 7:36
  • \$\begingroup\$ @ICanHazHats Correct, I fixed it, thanks. \$\endgroup\$ – Fatalize Dec 18 '15 at 8:35
1
\$\begingroup\$

J, 29 bytes

3 :'<.0.5+|:(-/ .**%.)1e_9+y'

Same epsilon/inverse/determinant trick. From right to left:

  • 1e_9+ adds an epsilon,
  • (-/ .**%.) is determinant (-/ .*) times inverse (%.),
  • |: transposes,
  • <.0.5+ rounds.
\$\endgroup\$
5
\$\begingroup\$

Matlab, 42 33 bytes

Using an anonymous function:

@(A)round(inv(A+eps)'*det(A+eps))

Input and output are matrices (2D numeric arrays).

eps is added in case the matrix is singular. It is "removed" using round (the true result is guaranteed to be an integer).

Example:

>> @(A)round(inv(A+eps)'*det(A+eps))
ans = 
    @(A)round(inv(A+eps)'*det(A+eps))
>> ans([-3,2,-5; -1,0,-2; 3,-4,1])
ans =
-8    -5     4
18    12    -6
-4    -1     2

Example with singular matrix:

>> @(A)round(inv(A+eps)'*det(A+eps))
ans = 
    @(A)round(inv(A+eps)*det(A+eps)')
>> ans([1,0 ; 0,0])
ans =
     0     0
     0     1

Or try it online in Octave.

\$\endgroup\$
  • 2
    \$\begingroup\$ However I do have a concern that I haven't talked about in the challenge: this answer assumes that the input matrix is invertible. Using your code on say [1,0 ; 0,0] gives an error when it should output [0,0 ; 0,1] \$\endgroup\$ – Fatalize Dec 16 '15 at 14:58
  • 1
    \$\begingroup\$ Since you are returning from a function, I don't think you should need mat2str: "resulting cofactor matrix may be... returned from a function" \$\endgroup\$ – FryAmTheEggman Dec 16 '15 at 15:47
  • 1
    \$\begingroup\$ @FryAmTheEggman Thanks! But "The cofactor matrix must be formatted in the exact same way the input matrices are given". That's why I think I need mat2str \$\endgroup\$ – Luis Mendo Dec 16 '15 at 15:52
  • 1
    \$\begingroup\$ @Fatalize Yes, it's that. eps is about 1e-16. So it makes the matrix non-singular (but very ill-conditioned). The result is not exactly integer; so fix (round towards zero) fixes that. This works provided the error doesn't exceed .5. I'm afraid there are no guarantees. For very large integers it might fail. I said it was a dirty trick :-P \$\endgroup\$ – Luis Mendo Dec 16 '15 at 15:55
  • 1
    \$\begingroup\$ @Fatalize for clarity, could you say whether mat2str is needed here? To me it feels like since this is a function, the input actually is the unformatted matrix. Like if you try f=... then do f(f(...)) this won't work, but removing mat2str makes that work fine. \$\endgroup\$ – FryAmTheEggman Dec 16 '15 at 16:39
4
\$\begingroup\$

Mathematica, 27 35 bytes

Thread[Det[#+x]Inverse[#+x]]/.x->0&
\$\endgroup\$
  • \$\begingroup\$ Does this work for non-invertible matrices, e.g. [[1,0],[0,0]]? \$\endgroup\$ – Fatalize Dec 16 '15 at 15:53
  • \$\begingroup\$ @FryAmTheEggman That doesn't seem to work. \$\endgroup\$ – LegionMammal978 Dec 16 '15 at 23:00
3
\$\begingroup\$

R, 121 94 bytes

function(A)t(outer(1:(n=NROW(A)),1:n,Vectorize(function(i,j)(-1)^(i+j)*det(A[-i,-j,drop=F]))))

This is an absurdly long function that accepts an object of class matrix and returns another such object. To call it, assign it to a variable.

Ungolfed:

cofactor <- function(A) {
    # Get the number of rows (and columns, since A is guaranteed to
    # be square) of the input matrix A
    n <- NROW(A)

    # Define a function that accepts two indices i,j and returns the
    # i,j cofactor
    C <- function(i, j) {
        # Since R loves to drop things into lower dimensions whenever
        # possible, ensure that the minor obtained by column deletion
        # is still a matrix object by adding the drop = FALSE option
        a <- A[-i, -j, drop = FALSE]

        (-1)^(i+j) * det(a)
    }

    # Obtain the adjugate matrix by vectorizing the function C over
    # the indices of A
    adj <- outer(1:n, 1:n, Vectorize(C))

    # Transpose to obtain the cofactor matrix
    t(adj)
}
\$\endgroup\$
  • \$\begingroup\$ 80 bytes using mapply instead of outer and Vectorize \$\endgroup\$ – Giuseppe Sep 17 '17 at 19:15
2
\$\begingroup\$

GAP, 246 Bytes

You can tell this is good coding by the triple nested for-loops.

It's pretty straightforward. GAP doesn't really have the same tools to deal with matrices that other math oriented languages do. The only thing really used here is the built in determinant operator.

f:=function(M)local A,B,i,j,v;A:=StructuralCopy(M);if not Size(M)=1 then for i in [1..Size(M)] do for j in [1..Size(M)] do B:=StructuralCopy(M);for v in B do Remove(v,j);od;Remove(B,i);A[i][j]:= (-1)^(i+j)*DeterminantMat(B);od;od;fi;Print(A);end;

ungolfed:

f:=function(M)
    local A,B,i,j,v;
    A:=StructuralCopy(M);
    if not Size(M)=1 then
        for i in [1..Size(M)] do
            for j in [1..Size(M)] do
                B:=StructuralCopy(M);
                for v in B do
                    Remove(v,j);
                od;
                Remove(B,i);
                 A[i][j]:= (-1)^(i+j)*DeterminantMat(B);
            od;
        od;
    fi;
    Print(A);
end;
\$\endgroup\$

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.