11
\$\begingroup\$

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 . You may not take input as 1d array, it must be 2d array if your language has a builtin 2d arrays.

\$\endgroup\$
9
  • \$\begingroup\$ Is the input matrix guaranteed to contain only 1 and -1? \$\endgroup\$
    – Arnauld
    Commented Jul 7 at 21:19
  • \$\begingroup\$ @Arnauld yeah, only 1 and -1. No zeros. \$\endgroup\$
    – Fmbalbuena
    Commented Jul 7 at 21:21
  • \$\begingroup\$ Is the input guaranteed to be square? \$\endgroup\$
    – chunes
    Commented Jul 7 at 21:33
  • 1
    \$\begingroup\$ You may not take input as 1d array, it must be 2d array - What about languages (like C) that don't have builtin 2d arrays? \$\endgroup\$
    – Noodle9
    Commented Jul 7 at 21:52
  • 2
    \$\begingroup\$ Please edit the challenge to reflect the input restrictions (only plus/minus 1 values, matrix is square). They are too important to be buried in comments \$\endgroup\$
    – Luis Mendo
    Commented Jul 7 at 22:14

14 Answers 14

7
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Oh, duh. I'm too rusty! \$\endgroup\$
    – Giuseppe
    Commented Jul 9 at 11:39
6
\$\begingroup\$

Vyxal, 7 bytes

ÞḊ²$@Π=

Try it Online! -1 thanks to att.

ÞḊ      # Is determinant 
  ²     # squared
      = # equal to
   $@   # Length of input
     Π  # To the power of itself?
\$\endgroup\$
1
  • 2
    \$\begingroup\$ -1 with det ÞḊ²$@Π= \$\endgroup\$
    – att
    Commented Jul 9 at 6:36
5
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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()
\$\endgroup\$
0
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
0
3
\$\begingroup\$

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.

screenshot

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.

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 22 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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)
New contributor
DPD- is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ null y can be y==[] \$\endgroup\$
    – xnor
    Commented Jul 9 at 3:54
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

Ruby, 58 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ This doesn't work for e.g. ⍉4 4⍴1 1 1 ¯1 \$\endgroup\$
    – att
    Commented Jul 9 at 5:07
  • \$\begingroup\$ @att. Thanks. Hopefully fixed. \$\endgroup\$
    – Graham
    Commented Jul 9 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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