17
\$\begingroup\$

Note that this challenge requires no handling or understanding of complex numbers.

Given a non-empty square matrix where every element is a two-element (Re,Im) integer list, determine (giving any truthy/falsy values or any two consistent values) whether this represents a Hermitian matrix.

Note that the input is a 3D array of integers; not a 2D array of complex numbers. If your language cannot take a 3D array directly, you may take a flat list (and the n×n or n×n×2 shape if that helps).

A matrix is Hermitian if it equals its own conjugate transpose. In other words, if you flip it across its top-left to bottom-right diagonal and negate the second element of all the two-element leaf-lists, it is identical to the input matrix. Note that the order of flipping and negating is irrelevant, so you may negate first, and flip afterwards.

Walk-though example

This example uses JSON with superfluous white-space to ease reading:

[[ [2, 0] , [2, 1] , [4, 0] ],
 [ [2,-1] , [3, 0] , [0, 1] ],
 [ [4, 0] , [0,-1] , [1, 0] ]]

Transpose (flip across NW—SE diagonal):

[[ [2, 0] , [2,-1] , [4, 0] ],
 [ [2, 1] , [3, 0] , [0,-1] ],
 [ [4, 0] , [0, 1] , [1, 0] ]]

Negate second elements of leaf-lists:

[[ [2, 0] , [2, 1] , [4, 0] ],
 [ [2,-1] , [3, 0] , [0, 1] ],
 [ [4, 0] , [0,-1] , [1, 0] ]]

As this is identical to the input, the matrix is Hermitian.

Test cases

Hermitian

[[[2,0],[2,1],[4,0]],[[2,-1],[3,0],[0,1]],[[4,0],[0,-1],[1,0]]]

[[[1,0],[2,0]],[[2,0],[1,0]]]

[[[1,0],[2,-3]],[[2,3],[1,0]]]

[[[42,0]]]

Non-Hermitian

[[[2,0],[2,1],[4,0]],[[2,-1],[3,0],[0,1]],[[4,0],[0,-1],[1,-1]]]

[[[0,1],[0,2]],[[0,2],[0,1]]]

[[[1,0],[2,3]],[[2,3],[1,0]]]

[[[3,2]]]

\$\endgroup\$
  • \$\begingroup\$ @LuisMendo I'm still thinking. Any ideas? \$\endgroup\$ – Adám Feb 26 '18 at 14:38
  • \$\begingroup\$ For the record, a new Meta-post. (I haven't voted to close, but I see someone has, so I'm curious what the community thinks about this). \$\endgroup\$ – Stewie Griffin Feb 26 '18 at 15:06
  • 5
    \$\begingroup\$ @Adám I would make it as explicit as possible, but it's up to you. Flexibility in input and output formats is usually desired, but cannot be inferred by default, specially when you say the input is a 3D array of real numbers; not a 2D array of complex numbers. It's not clear how broad your concept of 3D array input format is \$\endgroup\$ – Luis Mendo Feb 26 '18 at 16:04
  • 3
    \$\begingroup\$ @Adám Can a pair of 2D matrices (one for real part, one for imaginary part) be taken as input? \$\endgroup\$ – dylnan Feb 26 '18 at 16:53
  • 1
    \$\begingroup\$ @dylnan No. Input has to be a single structure representing some sort of 3-dimensionality where the leaf dimension contains the Re-Im pairs. \$\endgroup\$ – Adám Feb 26 '18 at 18:55

19 Answers 19

10
\$\begingroup\$

R, 71 48 47 bytes

function(A)all(Conj(t(B<-A[,,1]+A[,,2]*1i))==B)

Takes a 3D array of real numbers, make a 2D array of imaginary numbers, transpose, conjugate and compare.

Thanks to @Giuseppe for reducing the byte count by an astounding 23 bytes, and to @Vlo for the final 1!

Try it online!

Example:

> A <- array(c(2,2,4,2,3,0,4,0,1,0,-1,0,1,0,-1,0,1,0),dim=c(3,3,2))
> A
, , 1

     [,1] [,2] [,3]
[1,]    2    2    4
[2,]    2    3    0
[3,]    4    0    1

, , 2

     [,1] [,2] [,3]
[1,]    0    1    0
[2,]   -1    0    1
[3,]    0   -1    0

> f <- function(A)all(Conj(t(B<-A[,,1]+A[,,2]*1i))==B)
> f(A)
[1] TRUE
\$\endgroup\$
  • 1
    \$\begingroup\$ B=A[,,1]+A[,,2]*1i should save a few bytes. \$\endgroup\$ – Giuseppe Feb 26 '18 at 14:59
  • \$\begingroup\$ @GIuseppe arf I thought i tried that but apparently not. Thanks! \$\endgroup\$ – plannapus Feb 26 '18 at 15:00
  • 1
    \$\begingroup\$ Also, isSymmetric exists and works for Hermitian complex matrices but the 1x1 case is tricky since [ drops attributes and it results in a complex rather than a matrix \$\endgroup\$ – Giuseppe Feb 26 '18 at 15:02
  • 2
    \$\begingroup\$ function(A)all(Conj(t(B<-A[,,1]+A[,,2]*1i))==B) In-line assignment saves 1. \$\endgroup\$ – Vlo Feb 27 '18 at 15:53
7
\$\begingroup\$

Octave, 39 34 31 bytes

@(x)(y=x(:,:,1)+j*x(:,:,2))==y'

Try it online!

Saved 3 bytes thanks to Luis Mendo who informed me about the clarifications in the challenge text.

Explanation:

In MATLAB and Octave, ' is the conjugate complex transpose, not the "regular" transpose.

We create a variable y inline that's the first layer of the 3D matrix plus the second layer multiplied with the complex unit j, i.e. a complex matrix where the real term is the first "layer", and the imaginary is the second "layer". We then check if it equals itself complex conjugate transposed.

This will output a matrix containing only 1 if true, and a matrix containing at least one 0 if false. These are considered true and false in Octave (Proof).

\$\endgroup\$
6
\$\begingroup\$

Python 2, 50 bytes

lambda m:[[[a,-b]for a,b in l]for l in zip(*m)]==m

Try it online!

\$\endgroup\$
5
\$\begingroup\$

APL (Dyalog Unicode), 22 15 9 7 bytes

⍉≡⊢∘-\¨

Try it online!

Tacit prefix function.

Thanks to Adám for 7 bytes on the Dfn, and to both Adám and ErikTheOutgolfer for putting up with my stupidity helping me find the tacit version.

Thanks to ngn for 2 bytes on the tacit version.

How?

⍉≡⊢∘-\¨ ⍝ Anonymous tacit function.
      ¨ ⍝ Apply to each element of the argument:
     \  ⍝ Cumulative reduction, using
  ⊢∘-   ⍝ Ignore the first element, then negate the second
 ≡      ⍝ And match
⍉       ⍝ To the argument's transposition.
\$\endgroup\$
5
\$\begingroup\$

Wolfram Language (Mathematica), 45 34 33 26 21 18 bytes

#==#&[#.{1,I}]&

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 34 bytes: Try it online! \$\endgroup\$ – JungHwan Min Feb 26 '18 at 16:21
  • \$\begingroup\$ @alephalpha Thanks a lot; I know that 0xf3c7 is the transpose operator, but what is 0xf3c8? \$\endgroup\$ – Jonathan Frech Feb 26 '18 at 17:53
  • 1
    \$\begingroup\$ @alephalpha There is also 0xf3c9 (Wolfram Documentation). \$\endgroup\$ – Jonathan Frech Feb 26 '18 at 18:00
4
\$\begingroup\$

Java 8, 137 136 134 126 119 bytes

m->{int r=1,l=m.length,i=l,j;for(;i-->0;)for(j=l;j-->0;)r=m[i][j][0]!=m[j][i][0]|m[i][j][1]!=-m[j][i][1]?0:r;return r;}

Returns 1 if Hermitian, 0 otherwise.

Explanation:

Try it online.

m->{                 // Method with 3D integer-array as parameter and boolean return-type
  int r=1,           //  Flag-integer `r`, starting at 1
      l=m.length,    //  The size of the 3D input array
      i=l,j;         //  Index-integers
  for(;i-->0;)       //  Loop over the rows
    for(j=l;j-->0;)  //   Inner loop over the columns
      r=m[i][j][0]!=m[j][i][0] 
                     //    If the first numbers diagonally aren't equal,
        |m[i][j][1]!=-m[j][i][1]?
                     //    or the second numbers aren't negatives of each other:
         0           //     Set the flag `r` to 0
        :            //    Else:
         r;          //     Leave the flag `r` the same
  return r;}         //  Return the flag `r`
\$\endgroup\$
3
\$\begingroup\$

J, 14 bytes

[:(+-:|:)j./"1

Try it online!

Explanation

[:(+-:|:)j./"1  Input: 3d array
         j./"1  Reduce by complex combine at rank 1
[:              Cap, operate on the 2d array of complex values
   +              Conjugate
      |:          Transpose
    -:            Match?
\$\endgroup\$
  • \$\begingroup\$ Also 14: -:0 2|:(,-)/"1 \$\endgroup\$ – FrownyFrog Feb 27 '18 at 7:58
3
\$\begingroup\$

Haskell, 50 bytes

-7 bytes thanks to H.PWiz.

(==)<*>map(map((0-)<$>)).foldr(zipWith(:))e
e=[]:e

Try it online!

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

Jelly,  6  5 bytes

Z×Ø+⁼

A monadic link returning 1 for a Hermitian input and 0 otherwise.

Try it online!

How?

Z×Ø+⁼ - Link: list of lists of lists, M
Z     - transpose
  Ø+  - literal = [1,-1]
 ×    - multiply (vectorises)
    ⁼ - equal to M?
\$\endgroup\$
  • \$\begingroup\$ I believe modern Jelly has Ø+. \$\endgroup\$ – lirtosiast Dec 11 '18 at 14:15
  • \$\begingroup\$ @lirtosiast indeed you are correct, updated to use it; thanks! \$\endgroup\$ – Jonathan Allan Dec 11 '18 at 19:02
2
\$\begingroup\$

05AB1E, 9 bytes

øεεX®‚*]Q

Try it online!

Explanation

ø           # transpose
 ε          # apply to each 2-d array
  ε         # apply to each pair
   X®‚*     # multiply by [1,-1]
       ]    # end apply(s)
        Q   # compare to input for equality
\$\endgroup\$
2
\$\begingroup\$

Ruby, 46 bytes

->m{m.transpose.map{|l|l.map{|a,b|[a,-b]}}==m}

Try it online!

Port of my Python answer

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

Perl 5, -a0 48 bytes

Old counting: 50 bytes (+2 for a0). Not bad for a language that has no builtin transpose (I'm not jealous at all, no sirree)

Give the input matrix on STDIN with , between the real and imaginary part, so e.g.:

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

Will print 1 for hermitian, nothing otherwise

#!/usr/bin/perl -a0
say@F~~[map/(\S+,)(\S+)/gc?$1.-$2:(),(/.+/g)x@F]

Try it online!

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

Husk, 7 bytes

=¹mmṀ_T

Try it online!

How?

Note that should work instead of mm , but there's an annoying bug that prevents me from using it :(

=¹mmṀ_T – Full program. Takes input from Command line args, as a list of lists of tuples.
  m   T – For each list in the input's tranpose...
   mṀ_  – ... Negate the last value of each tuple they contain.
=¹      – Check whether this is the same as the input.
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 53 bytes

Saved 2 bytes thanks to @Neil

Returns false for Hermitian or true for non-Hermitian.

m=>m.some((r,y)=>r.some(([a,b],x)=>m[x][y]!=a+[,-b]))

Try it online!

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

C (gcc), 107 103 100 bytes

  • Saved four bytes thanks to Steadybox; golfed A[0] to *A twice.
  • Saved three bytes thanks to ceilingcat.
j,k,r;f(A,s)int***A;{for(r=0,j=s;j--;)for(k=s;k--;)r|=*A[j][k]-*A[k][j]|A[j][k][1]+A[k][j][1];A=!r;}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 103 bytes \$\endgroup\$ – Steadybox Feb 26 '18 at 15:53
  • \$\begingroup\$ @Steadybox Thanks a lot. Funny ... A few hours ago I had exactly this golf in mind -- dereferencing instead of indexing -- but simply forgot ... \$\endgroup\$ – Jonathan Frech Feb 26 '18 at 16:06
  • \$\begingroup\$ @ceilingcat Thank you. \$\endgroup\$ – Jonathan Frech Aug 1 at 0:04
0
\$\begingroup\$

Actually, 13 bytes

┬⌠⌠Çá╫k⌡M⌡Mß=

Try it online!

How it works?

This submission actually makes use of complex numbers. If taking input as a matrix of complex entries was allowed, then it would be 8 bytes.

┬⌠⌠Çá╫k⌡M⌡Mß=  –> Full program.
┬              –> Transpose.
 ⌠       ⌡M    –> For each list in the input's transpose do the following:
  ⌠    ⌡M         –> For each two-element list of the form [a, b]...
   Ç              –> Turn it into a complex number (a+bi).
    á             –> Find its complex conjugate: Push (a-bi).
     ╫k           –> Push [Re(N), Im(N)], so [a, -b].
           ß=  –> Check whether the result equals the input.
\$\endgroup\$
0
\$\begingroup\$

Pyth, 9 bytes

qCmm,hk_e

Explanation:

qCmm,hk_ekdQQ  Autofill variables
    ,hk_ek     [a,-b]...
  mm      dQ    ...for each [a,b] in the input (m...Q)'s rows (m...d).
 C             Transpose.
q           Q  Is this result equal to the original?

Test suite.

\$\endgroup\$
  • \$\begingroup\$ Your answer is actually 9 bytes... A 9-byte alternative: qCmm*V_B1. \$\endgroup\$ – Mr. Xcoder Feb 27 '18 at 6:32
  • \$\begingroup\$ I golfed off one byte as I was making the submission, from qCmm.e_Fbk... apparently I forgot to edit the byte count in the final submission. @Mr.Xcoder I fixed it regardless, thanks for the catch! \$\endgroup\$ – Steven H. Feb 27 '18 at 16:12
0
\$\begingroup\$

C,  111   110  108 bytes

Thanks to @Jonathan Frech for saving a byte and thanks to @ceilingcat for saving two bytes!

i,j,r;f(A,n)int*A;{for(r=i=0;i<n*2;i+=2)for(j=n*2;j;r|=A[i*n+j]-A[j*n+i]|A[i*n-~j]+A[j*n-~i])j-=2;return!r;}

Try it online!

C (gcc),  106  104 bytes

i,j,r;f(A,n)int*A;{for(r=i=0;i<n*2;i+=2)for(j=n*2;j;r|=A[i*n+j]-A[j*n+i]|A[i*n-~j]+A[j*n-~i])j-=2;A=!r;}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I think r|=...|... works as well as r+=...||.... \$\endgroup\$ – Jonathan Frech Feb 26 '18 at 15:37
  • \$\begingroup\$ @JonathanFrech Yes, it does. Thanks! \$\endgroup\$ – Steadybox Feb 26 '18 at 15:38
0
\$\begingroup\$

Actually, 13 bytes

;┬⌠⌠d±@q⌡M⌡M=

Try it online!

Explanation:

;┬⌠⌠d±@q⌡M⌡M=
;              make a copy
 ┬             transpose copy
  ⌠⌠d±@q⌡M⌡M   for each row:
   ⌠d±@q⌡M       for each cell in row:
    d              remove last element from list
     ±             swap sign
      @q           insert at end of list
            =  compare equality with original
\$\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.