Is this a Hadamard matrix?

Question

Hadamard matrices is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal.

In other words, it means that each pair of rows has matching entries in exactly half of their columns and mismatched entries in the remaining columns. As a result, the same properties hold for columns as well as rows.

Examples

[ 1  1  1  1
  1 -1  1 -1
  1  1 -1 -1
  1 -1 -1  1 ]

This is a Hadamard matrix, because any pair of rows has matching entries in exactly half of their columns, like:

[ 1  1  1  1
  |  /  |  /
  1 -1  1 -1
             ]

There are 2 |s (matching entries) and 2 /s (mismatched entries). The same logic also applies by columns:

[ 1  ―  1   
  1  ―  1   
  1  ~ -1   
  1  ~ -1    ]

There are two ―s (matching entries) and two ~s (mismatched entries).

This logic can be applied to every pair of rows and columns.

Another example:

[ 1  1
  1 -1 ]

This is a hadamard matrix, because there is only one pair of rows and one pair of columns, but their matching entries is still half of the size of the matrix.

A counterexample like:

[  1 -1  1 -1
  -1  1 -1  1
   1 -1  1 -1
  -1  1 -1  1 ]

is not a Hadamard matrix, because two pair of rows match in all columns, and four rows don't match in any column. The same logic applies to pair of columns.

Note that

[ 1 ]

is also a Hadamard (1x1) matrix, and your code should handle that (See challenge).

Notes

• The matrix inputs are always square

• The matrix will only contain -1 or 1. No zeros.

Challenge

The shortest answer that checks if a matrix is a Hadamard matrix wins, because this is code-golf. You may not take input as 1d array, it must be 2d array if your language has a builtin 2d arrays.

Answer 1

R, 36 bytes

\(H)any(H%*%t(H)-diag(n<-nrow(H))*n)

Attempt This Online!

Uses the characterization: \$HH^T=nI_n\$.

Outputs swapped TRUE/FALSE.

Answer 2

Vyxal, 7 bytes

ÞḊ²$@Π=

Try it Online! -1 thanks to att.

ÞḊ      # Is determinant 
  ²     # squared
      = # equal to
   $@   # Length of input
     Π  # To the power of itself?

Answer 3

Nekomata + -e, 4 bytes

Sđ∙Z

Attempt This Online!

This swaps truthy and falsy values. It outputs False if the input is a Hadamard matrix, and True otherwise.

Sđ∙Z
S       Find a subset of the input
 đ      whose length is 2
  ∙     and the dot product of the two elements
   Z    is nonzero

-e checks if there is a solution.

---

Nekomata + -e, 6 bytes

ᵒ∙jZ‼*

Attempt This Online!

ᵒ∙jZ‼*
ᵒ∙      Outer product with dot product
        This is equivalent to multiplying the matrix by its transpose
  j     Join the matrix into a single list
   Z‼   Remove zeros
     *  Check if it has the same length as the input
        Nekomata does not allow multiplying two lists of different lengths

Answer 4

JavaScript (ES6), 60 bytes

Returns false for Hadamard or true for non-Hadamard.

m=>m.some(p=>m.some(q=>p!=q&&p.reduce((t,v,x)=>t+v*q[x],0)))

Try it online!

Commented

m =>                // m[] = input matrix
m.some(p =>         // for each row p[] in m[]:
  m.some(q =>       //   for each row q[] in m[]:
    p != q &&       //     test whether p[] is not equal to q[]
                    //     (comparison of pointers)
    p.reduce(       //     for each value v at position x in p[],
    (t, v, x) =>    //     using t as the accumulator:
      t + v * q[x], //       add v * q[x] to the accumulator,
                    //       which gives 1 if v = q[x] or -1 otherwise
      0             //       start with t = 0
    )               //     end of reduce() -> gives 0 if and only if
                    //     exactly half of the values are matching
  )                 //   end of inner some()
)                   // end of outer some()

Answer 5

MATL, 9 7 bytes

Thanks to @alephalpha for a correction (the transpose was originally missing).

t!Y*XR~

Inputs a matrix. Outputs a a matrix of ones (which is truthy) if the input is a Hadamard matrix, or a matrix containing at least a zero (which is falsy) otherwise.

Try it online! Or verify all test cases.

How it works

t     % Implicit input: matrix M, of size n, with 1 or −1 entries. Duplicate
!     % Transpose
Y*    % Matrix product. This is a scalar matrix if and only if M is Hadamard
XR    % Set entries on the diagonal and below to 0
~     % Negate each entry. Implicit display

Answer 6

Google Sheets, 51 bytes

lambda(a,b,sum(byrow(b,lambda(r,sumproduct(a,r)))))

This is a Google Sheets lambda function that expects two parameters: a should point to a 1D array that contains the first row in the matrix, and b should point to a 2D array that holds the rest of the rows in the matrix.

The function assumes that the matrix in the format specified in the question, and returns 0 if it is a Hadamard matrix and a non-zero value otherwise. In the event of a 1x1 matrix like [1], a should point to the matrix and b should point to a null array of zero rows, and the formula will return 0.

You can call the function like this:

=lambda(a, b, 
  sum(byrow(b, lambda(r, sumproduct(a, r)))) 
)(A1:D1, A2:D4)

...where a is A1:D1 and bis A2:D4.

Answer 7

Charcoal, 12 bytes

⊙θ⊙θ∧⁻κμΣ×ιλ

Attempt This Online! Link is to verbose version of code. Outputs an inverted Charcoal boolean, i.e. - if not Hadamard, nothing if Hadamard, Explanation:

⊙               Input array
 θ              Any row satisfies
  ⊙             Input array
   θ            Any row satisfies
      κ         Outer index
     ⁻          Does not equal
       μ        Inner index
    ∧           Logical And
          ι     Outer row
         ×      Vectorised product with
           λ    Inner row
        Σ       Has nonzero sum
                Implicitly print

Answer 8

PARI/GP, 11 bytes

a->a*a~==#a

Attempt This Online!

Let \$A\$ be the input matrix. Since it is guaranteed to contain only 1 and -1, we only need to check if \$A A^T = n I\$, where \$n\$ is the number of rows in \$A\$. When comparing a matrix with a scalar, PARI/GP will automatically multiply the scalar by the identity matrix of the same size.

Answer 9

Wolfram Language (Mathematica), 22 bytes

#^#&@Tr[1^#]==Det@#^2&

Try it online!

Answer 10

Python 3, 105 bytes

f=lambda a,x=2:x<1or all(sum(map(int.__eq__,i,j))*2==len(i)for i in a for j in{*a}-{i})*f([*zip(*a)],x-1)

Try it online!

Answer 11

05AB1E, 11 10 bytes

δ*OZ/āDδQQ

Port of @alephalpha's PARI/GP answer, so make sure to upvote that answer as well!

Try it online or verify all test cases.

Explanation:

δ*O        # Matrix multiplicate the (implicit) input with itself:
δ          #  Apply double-vectorized, using two times the (implicit) input-matrix:
 *         #   Vectorized multiply
  O        #  Sum each inner row together
   Z       # Push the flattened maximum (without popping the matrix)
    /      # Divide each inner value by this maximum
     āDδQ  # Push an identity-matrix of the same size:
     ā     #  Push a list in the range [1,length] (without popping)
      D    #  Duplicate it
       δ   #  Apply double-vectorized again:
        Q  #   Check whether the values are equal
         Q # Check if the earlier matrix equals the identity-matrix
           # (after which the result is output implicitly)

Answer 12

Haskell, 47, 46 bytes

• -1 byte thanks to xnor

f(x:y)=[]==y||all((0==).sum.zipWith(*)x)y&&f y

Try it online!

• sum.zipWith(*) computes the scalar product of two vectors
• x is the first row, y all the next rows
• we check that for all other rows in y the scalar product with the current row x is zero
• then we repeat the check discarding the first row (Haskell works well with recursion)

Answer 13

Ruby, 58 bytes

->m{m.combination(2).all?{|r,s|s.zip(r).sum{|a,b|a*b}==0}}

Try it online!

Answer 14

APL+WIN, 19 20 bytes

+1 to fix problem identified by att

Prompts for matrix. 1 = true, 0 = false

(×/⍴m)=+/+/|m+.×⍉m←⎕

Try it online! Thanks to Dyalog Classic

Answer 15

Haskell + hgl, 19 bytes

mF(q0<sm)<xQ(zW ml)

Attempt This Online!

Explanation

This takes all pairs of rows \$(a,b)\$ where \$a\$ comes before \$b\$, computes the dot product and checks that the result is always zero.

• xQ computes the pairs
• zW ml multiplies the rows pairwise
• sm performs the sum to get the dot product
• q0 compares it to zero
• mF folds using logical and.

Reflection

I'm pretty pleased with this overall. The library is not really built with a lot of linear algebra functions (yet). So this is not a task I should expect this to do very well at. It's not stellar, but it is passable considering everythign. I'm very happy that xQ exists.

• There could be a dot product builtin. This would make this much shorter.
• xQ should be refactored to take a foldable so this could operate on actual vector types instead of lists.

Answer 16

Setanta, 102 bytes

gniomh(m){b:=0le i idir(0,fad@m)le j idir(0,i){s:=0le k idir(0,fad@m)s+=m[i][k]*m[j][k]b=b|s}toradh!b}

try-setanta.ie link

Answer 17

Raku (Perl 6) (rakudo), 38 bytes

{!grep {[+] [Z*] $_},.combinations(2)}

Attempt This Online!