Alternating sign matrix verification

Question

An alternating sign matrix is an n by n matrix consisting of the numbers -1, 0, 1, such that:

• The sum of each row and column is 1
• The nonzero entries in each row and column alternate in sign

These matrices generalise permutation matrices, and the number of such matrices for a given n was of interest for some time. They occur naturally during the Dodgson condensation method of computing matrix determinants (named after Charles Dodgson, better known as Lewis Carroll).

Here are some examples of 4 by 4 alternating sign matrices:

 0  1  0  0          1  0  0  0          0  0  1  0          0  0  1  0    
 0  0  1  0          0  0  1  0          0  1 -1  1          1  0 -1  1
 1  0  0  0          0  1 -1  1          1 -1  1  0          0  1  0  0
 0  0  0  1          0  0  1  0          0  1  0  0          0  0  1  0

And here are some examples of 4 by 4 matrices which aren't alternating sign matrices:

 0  1  0  0
 0  0  0  1
 1  0  0  0
 0  0  1 -1    (last row and last column don't add to 1)

 0  0  0  1
 1  0  0  0
-1  1  1  0
 1  0  0  0    (third row does not alternate correctly)

Your program or function will be given an n by n matrix (n >= 1) of -1s, 0s and 1s — output a truthy value if the given matrix is an alternating sign matrix, otherwise output a falsy value.

This is code-golf, so the goal is to minimise the number of bytes used.

Test cases

The following test cases are given in a Python-like 2D list format.

Truthy:

[[1]]
[[1,0],[0,1]]
[[0,1],[1,0]]
[[0,1,0],[0,0,1],[1,0,0]]
[[0,1,0],[1,-1,1],[0,1,0]]
[[0,1,0,0],[0,0,1,0],[1,0,0,0],[0,0,0,1]]
[[1,0,0,0],[0,0,1,0],[0,1,-1,1],[0,0,1,0]]
[[0,0,1,0],[0,1,-1,1],[1,-1,1,0],[0,1,0,0]]
[[0,0,1,0],[1,0,-1,1],[0,1,0,0],[0,0,1,0]]
[[0,0,1,0,0],[0,1,-1,1,0],[1,-1,1,0,0],[0,1,0,-1,1],[0,0,0,1,0]]
[[0,0,1,0,0,0,0,0],[1,0,-1,0,1,0,0,0],[0,0,0,1,-1,0,0,1],[0,0,1,-1,1,0,0,0],[0,0,0,0,0,0,1,0],[0,0,0,0,0,1,0,0],[0,1,-1,1,0,0,0,0],[0,0,1,0,0,0,0,0]]
[[0,0,0,0,1,0,0,0],[0,0,1,0,-1,1,0,0],[0,0,0,1,0,0,0,0],[1,0,0,-1,1,-1,1,0],[0,1,-1,1,-1,1,0,0],[0,0,0,0,1,0,0,0],[0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1]]

Falsy:

[[0]]
[[-1]]
[[1,0],[0,0]]
[[0,0],[0,1]]
[[-1,1],[1,0]]
[[0,1],[1,-1]]
[[0,0,0],[0,0,0],[0,0,0]]
[[0,1,0],[1,0,1],[0,1,0]]
[[-1,1,1],[1,-1,1],[1,1,-1]]
[[0,0,1],[1,0,0],[0,1,-1]]
[[0,1,0,0],[0,0,0,1],[1,0,0,0],[0,0,1,-1]]
[[0,0,1,0],[0,0,1,0],[1,0,-1,1],[0,1,0,0]]
[[0,0,0,1],[1,0,0,0],[-1,1,1,0],[1,0,0,0]]
[[1,0,1,0,-1],[0,1,0,0,0],[0,0,0,0,1],[0,0,0,1,0],[0,0,0,0,1]]
[[0,0,1,0,0],[0,1,-1,1,0],[1,-1,1,0,0],[0,1,1,-1,0],[0,0,-1,1,1]]
[[0,-1,0,1,1],[1,-1,1,-1,1],[0,1,1,0,-1],[1,1,-1,1,-1],[-1,1,0,0,1]]
[[0,0,1,0,0,0,0,0],[1,0,1,0,1,0,0,0],[0,0,0,1,-1,0,0,1],[0,0,1,-1,1,0,0,0],[0,0,0,0,0,0,1,0],[0,0,0,0,0,1,0,0],[0,1,-1,1,0,0,0,0],[0,0,1,0,0,0,0,0]]

Answer 1

Jelly, 15 bytes

;Zḟ€0;€-;@€-IFP

Try it online!

;Zḟ€0;€-;@€-IFP   Main monadic chain. Argument: z

;Z                Concatenate with its transpose.
  ḟ€0             Remove zeros from each sub-list. At this point,
                  one expects lists of the form [1, -1, 1, -1, ..., 1] for truthy,
                  and any other arrays containing purely 1 and -1 for falsey.
     ;€-          Append -1 to each sub-list.
        ;€@-      Prepend -1 to each sub-list.
            I     Compute the difference between each term. At this point,
                  for truthy, one expects arrays filled with 2, and arrays
                  containing 0 otherwise.
             FP   Product of every item. This checks if any item is equal to zero.

Answer 2

Retina, 62 58 56 53 bytes

Byte count assumes ISO 8859-1 encoding, and the \t should be replaced with actual tabs (0x09 which would be turned into spaces by SE otherwise).

$
\t$`¶
O$#`...(?<=^[^\t]*(.+))
$.1
T` 0
^(1(-11)*\s)+$

Input format is a matrix where each column uses three right-aligned characters, e.g.:

  0  0  1  0
  1  0 -1  1
  0  1  0  0
  0  0  1  0

Output is either 0 (falsy) or 1 (truthy).

Test suite. (The first few lines transform the input format and let Retina run several test cases at once.)

Explanation

Thankfully, the input is a square matrix: transposing squares is just about doable in Retina, whereas transposing rectangles is a massive pain.

$
\t$`¶

We start by appending a tab, the entire input again (using the prefix $`) and then a linefeed at the end (using Retina's alias ¶). We're using a tab to separate the two copies so that we can distinguish between them when we're transposing one of them, and by using a whitespace character we can save a couple of bytes later on.

O$#`...(?<=^[^\t]*(.+))
$.1

This is the trickiest bit: transposing the first copy of the matrix. The idea is to match cells in the first copy and then sorting them (stably) by the horizontal position. We match the cells with ... (since they're always three characters wide) and then measure the horizontal position with (.+) inside the lookbehind. Then, to make sure that we only transpose the first copy, we check that we can reach the beginning of the string without moving past a tab.

You might notice that this will also match some three-byte strings (that don't even align with the cells) in the first row of the second copy, because the .+ can pass through the tab. However, this is not an issue because the horizontal position of these matches is strictly greater than any inside the first copy, so these matches remain in their position.

The rest is fairly simple:

T` 0

We remove spaces and zeros from the input.

^(1(-11)*\s)+$

And finally we check that the entire input consists of whitespace-terminated rows of the form 1(-11)*, i.e. an alternating sequence of 1 and -1 that begins and ends with 1 (because otherwise it doesn't sum to 1).

Answer 3

Pyth, 16 bytes

!sm-sM._+d_1U2+C

Try it online: Demonstration or Test Suite

Explanation:

!sm-sM._+d_1U2+CQQ   two implicit Qs (=input matrix) at the end
              +CQQ   zip Q and connect it with Q (=list of columns and rows)
  m                  map each column/row d to:
        +d_1            append -1 to d
      ._                compute all prefixes of ^
    sM                  compute the sums of the prefixes
   -        U2          remove zeros and ones
                        a column/row is correct, if this gives an empty list 
 s                   connect up all resulting lists
!                    check, if this result is empty

Answer 4

Jelly, 11 bytes

;Zj-+\ṚQḄ=2

Returns 1 for alternating sign matrices, 0 otherwise. Try it online! or verify all test cases.

Background

Disregarding zeroes, each row and column has to consist of the pattern (1, -1)* 1, i.e., alternating occurrences of 1 and -1, starting and ending with a 1 (so the sum is 1).

To verify this is the case, we take the array of all rows and columns, and join them using -1 as separator. Since all endpoints are 1's, the resulting flat array satisfies the pattern (1, -1)* 1 if and only if the rows and columns do.

For the actual test, we compute the cumulative sum of the array. For an alternating sign matrix, the result will be an array of 0's and 1's that ends with a 1.

We reverse the cumulative sum and deduplicate it, keeping the order of the initial occurrences of all unique elements. For a truthy input, the result will be the list [1, 0].

To output the corresponding Boolean, we convert the duplicated cumulative sums from binary to integer and test if the result is 2.

How it works

;Zj-+\ṚQḄ=2  Main link. Argument: M (matrix / 2D array)

 Z           Zip; transpose M's rows and columns.
;            Concatenate M and zipped M.
  j-         Join, separating by -1.
    +\       Take the cumulative sum of the result.
      Ṛ      Reverse the array of partial sums.
       Q     Unique; deduplicate the partial sums.
        Ḅ    Unbinary; convert from base 2 to integer.
         =2  Test for equality with 2.

Answer 5

MATL, 18 16 15 13 bytes

3 bytes saved thanks to @Luis

t!h"@s1=@Xzdv

This solution accepts a 2D array as input and will output a truthy or falsey array. It is important to note that in MATL, a truthy array is composed of all non-zero elements while a falsey result has at least one zero element. Here is another demonstration of truthy/falsey arrays.

Try it Online

Modified version to show all test cases

Explanation

        % Implicitly grab input matrix
t!      % Duplicate and transpose input
h       % Horizontally concatenate input with transpose. This allows us to 
        % process only columns since now the columns *also* contain the rows.
"       % For each column (of our column/row combined matrix)
  @s1=  % Compute the sum and ensure it is equal to 1
  @Xz   % Get the non-zeros
  d     % Compute the element-to-element difference. The 1 and -1 alternate only if
        % all these differences are non-zero
  v     % Vertically concatenate everything on the stack
        % Implicit end of loop and implicitly display truthy/falsey value

Answer 6

Julia, 36 bytes

!x=[x^0 x^0;-x -x'][:]|>cumsum⊆0:1

Try it online!

Answer 7

JavaScript (ES6), 112 100 bytes

a=>!/(^|,)(?!0*10*(-10*10*)*(,|$))/.test(a.map(b=>b.join``)+','+a.map((_,i)=>a.map(b=>b[i]).join``))

Flattens the array and its transpose into strings, then (ignoring 0s) checks for the pattern 1-11...1-11 in each string.

Edit: Saved 12 bytes thanks to @PeterTaylor.

Answer 8

Python 2, 63 60 bytes

s=0;x=input()
for r in x+zip(*x):
 for n in(-1,)+r:s+=[n][s]

Input is a list of tuples.

This terminates with exit code 0 for alternating sign matrices and exit code 1 otherwise. This is what true and false do, and – as shown in the verification section – it can indeed be used as a condition in, e.g., a Bash script.

Verification

test-cases.txt

[(1,)]
[(1, 0), (0, 1)]
[(0, 1), (1, 0)]
[(0, 1, 0), (0, 0, 1), (1, 0, 0)]
[(0, 1, 0), (1, -1, 1), (0, 1, 0)]
[(0, 1, 0, 0), (0, 0, 1, 0), (1, 0, 0, 0), (0, 0, 0, 1)]
[(1, 0, 0, 0), (0, 0, 1, 0), (0, 1, -1, 1), (0, 0, 1, 0)]
[(0, 0, 1, 0), (0, 1, -1, 1), (1, -1, 1, 0), (0, 1, 0, 0)]
[(0, 0, 1, 0), (1, 0, -1, 1), (0, 1, 0, 0), (0, 0, 1, 0)]
[(0, 0, 1, 0, 0), (0, 1, -1, 1, 0), (1, -1, 1, 0, 0), (0, 1, 0, -1, 1), (0, 0, 0, 1, 0)]
[(0, 0, 1, 0, 0, 0, 0, 0), (1, 0, -1, 0, 1, 0, 0, 0), (0, 0, 0, 1, -1, 0, 0, 1), (0, 0, 1, -1, 1, 0, 0, 0), (0, 0, 0, 0, 0, 0, 1, 0), (0, 0, 0, 0, 0, 1, 0, 0), (0, 1, -1, 1, 0, 0, 0, 0), (0, 0, 1, 0, 0, 0, 0, 0)]
[(0, 0, 0, 0, 1, 0, 0, 0), (0, 0, 1, 0, -1, 1, 0, 0), (0, 0, 0, 1, 0, 0, 0, 0), (1, 0, 0, -1, 1, -1, 1, 0), (0, 1, -1, 1, -1, 1, 0, 0), (0, 0, 0, 0, 1, 0, 0, 0), (0, 0, 1, 0, 0, 0, 0, 0), (0, 0, 0, 0, 0, 0, 0, 1)]
[(0,)]
[(-1,)]
[(1, 0), (0, 0)]
[(0, 0), (0, 1)]
[(-1, 1), (1, 0)]
[(0, 1), (1, -1)]
[(0, 0, 0), (0, 0, 0), (0, 0, 0)]
[(0, 1, 0), (1, 0, 1), (0, 1, 0)]
[(-1, 1, 1), (1, -1, 1), (1, 1, -1)]
[(0, 0, 1), (1, 0, 0), (0, 1, -1)]
[(0, 1, 0, 0), (0, 0, 0, 1), (1, 0, 0, 0), (0, 0, 1, -1)]
[(0, 0, 1, 0), (0, 0, 1, 0), (1, 0, -1, 1), (0, 1, 0, 0)]
[(0, 0, 0, 1), (1, 0, 0, 0), (-1, 1, 1, 0), (1, 0, 0, 0)]
[(1, 0, 1, 0, -1), (0, 1, 0, 0, 0), (0, 0, 0, 0, 1), (0, 0, 0, 1, 0), (0, 0, 0, 0, 1)]
[(0, 0, 1, 0, 0), (0, 1, -1, 1, 0), (1, -1, 1, 0, 0), (0, 1, 1, -1, 0), (0, 0, -1, 1, 1)]
[(0, -1, 0, 1, 1), (1, -1, 1, -1, 1), (0, 1, 1, 0, -1), (1, 1, -1, 1, -1), (-1, 1, 0, 0, 1)]
[(0, 0, 1, 0, 0, 0, 0, 0), (1, 0, 1, 0, 1, 0, 0, 0), (0, 0, 0, 1, -1, 0, 0, 1), (0, 0, 1, -1, 1, 0, 0, 0), (0, 0, 0, 0, 0, 0, 1, 0), (0, 0, 0, 0, 0, 1, 0, 0), (0, 1, -1, 1, 0, 0, 0, 0), (0, 0, 1, 0, 0, 0, 0, 0)]

test-suite.sh

while read; do
        if python2 asmv.py <<< "$REPLY"; then
                echo "true"
        else
                echo "false"
        fi
done < test-cases.txt 2>&- | uniq -c

Output

$ bash test-suite.sh
     12 true
     17 false

How it works

Disregarding zeroes, each row and column has to consist of the pattern (1, -1)* 1, i.e., alternating occurrences of 1 and -1, starting and ending with a 1 (so the sum is 1).

To verify this is the case, we zip/transpose the input matrix M, append the result to M (now consisting of a list of rows and columns), and prepend a -1 to each row/column.

For example, if M is one of the following matrices (valid, invalid)

     0  1  0         0  0  0
     0  0  1         1  0  0
     1  0  0         0  1 -1

the results are

-1 | 0  1  0    -1 | 0  0  0
-1 | 0  0  1    -1 | 1  0  0
-1 | 1  0  0    -1 | 0  1 -1
------------    ------------
-1 | 0  0  1    -1 | 0  1  0
-1 | 1  0  0    -1 | 0  0  1
-1 | 0  1  0    -1 | 0  0 -1

Reading the generated matrix row-wise must result in a flat sequence with pattern (-1, 1)*. To verify this is the case, we take the cumulative sum of all entries, beginning with the top row.

For the example matrices, this results in

-1 -1  0  0 -1 -1 -1  0 -1  0  0  0 -1 -1 -1  0 -1  0  0  0 -1 -1  0  0
-1 -1 -1 -1 -2 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -2 -3 -3 -3 -2 -3 -3 -3 -4

For a valid alternating sign matrix, the output will consist of -1's and 0's and – since every -1 cancels out the previous 1 and vice versa – no other numbers.

At first glance, this may appear to fail checking if the last column ends with a 1. However, for an n × n matrix containing k zeroes, valid rows will contain n + k ones. If all columns except the last were valid as well, there would be n + k - 1 ones in the columns, which is impossible.

To test that there are no other numbers, we store the partial sums in a variable s and update them for each entry of with generated matrix with s+=[n][s].

If s = 0 or s = -1, this is equivalent to s+=n. However, for all other values of s, it causes an IndexError, so Python immediately terminates with exit code 1. If this doesn't happen at any point, the program finishes cleanly with exit code 0.

Answer 9

R, 54 bytes

Anonymous function, uses the same logic as Dennis's Python 2, Jelly, and Julia answers.

function(x)all(abs(cumsum(rbind(-1,cbind(t(x),x))))<2)