Properties of Binary Functions

Question

Many important topics in abstract algebra involve a binary function acting on a set. A number of properties of such functions have been defined in the investigation of such topics.

Your challenge will be to determine whether a given binary function on a given domain possesses five of these properties.

Properties

Closure

A binary function is closed if every possible output is in the domain.

Associativity

A binary function is associative if the order in which the function is applied to a series of inputs doesn't affect the result. That is, $ is associative if (a $ b) $ c always equals a $ (b $ c). Note that since the value (a $ b) is used as an input, associative functions must be closed.

Commutativity

A binary function is commutative if swapping the order of the inputs doesn't change the result. In other words, if a $ b always equals b $ a.

Identity

A binary function has an identity element if there exists some element e in the domain such that a $ e = a = e $ a for all a in the domain.

Idempotence

A binary function is idempotent if applying it to two identical inputs gives that number as the output. In other words, if a $ a = a for all a in the domain.

Input

You will be given a function in the form of a matrix, and the domain of the function will be the numbers 0 ... n-1, where n is the side length of the matrix.

The value (a $ b) is encoded in the matrix as the ath row's bth element. If the input matrix is Q, then a $ b = Q[a][b]

For example, the exponentiation function (** in Python) on the domain [0, 1, 2] is encoded as:

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

The left and right domains are the same, so the matrix will always be square.

You may use any convenient matrix format as input, such as a list of lists, a single list in row- or column- major order, your language's native matrix object, etc. However, you may not take a function directly as input.

For simplicity, the matrix entries will all be integers. You may assume that they fit in your language's native integer type.

Output

You may indicate which of the above properties hold in any format you choose, including a list of booleans, a string with a different character for each property, etc. However, there must be a distinct, unique output for each of the 24 possible subsets of the properties. This output must be easily human-readable.

Examples

The maximum function on domain n=4:

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

This function has the properties of closure, associativity, commutativity, identity and idempotence.

The exponentiation function on domain n=3:

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

This function has none of the above properties.

The addition function on domain n=3:

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

This function has the properties of commutativity and identity.

The K combinator on domain n=3:

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

This function has the properties of closure, associativity and idempotence.

The absolute difference function on domain n=3:

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

This function has the properties of closure, commutativity and identity.

The average function, rounding towards even, on domain n=3:

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

This function has the properties of closure, commutativity, identity and idempotence.

The equality function on domain n=3:

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

This function has the properties of closure and commutativity.

Challenge

This is code golf. Standard loopholes apply. Least bytes wins.

Answer 1

Pyth, 51 bytes

[qKUQ@VQKCIQ}]Km{@RdCBQKJ!-sQK&JqF.bsm@L@QdYN.p,sQK

Try it online: Demonstration or Test Suite

This prints a list of 5 boolean values. They indicate the properties in the order:

[Idempotence, Commutativity, Identity, Closure, Associativity]

Here is a better output format: Demonstration or Test Suite

Explanation:

Idempotence:

qKUQ@VQK
   Q       Q = input matrix
  UQ       [0, 1, ..., len(matrix)-1]
 K         assign to K
    @VQK   vectorized lookup of Q and K //gets the diagonal elements
qK         check, if this is equal to K

Commutativity:

CIQ   check if transpose(Q) is equal to Q

Identity:

}]Km{@RdCBQK
   m       K   map each d in K to:
        CBQ       the list [Q, transpose(Q)]
     @Rd          take the d-th element of each ^
    {             remove duplicates
}]K            check if [K] is in ^

Closure:

J!-sQK
   sQ    sum(Q) //all elements of Q
  -  K   remove the elements, that also appear in K
 !       ckeck, if the results in an empty list
J        store the result in J

Associativity:

&JqF.bsm@L@QdYN.p,sQK
               .p,sQK  all permutations of [sum(Q), K] //all 2 ;-)
    .b                 map each pair (N,Y) of ^ to:
       m      N           map each d of N to:
          @Qd                the row Q[d]
        @L   Y               map each element of Y to the corr. element in ^
      s                   unfold this 2-d list
  qF                   check if they result in identically lists
&J                     and J

Answer 2

Haskell, 178 171 bytes

import Data.List
f x=[c,c&&and[(m%n)%o==m%(n%o)|m<-b,n<-b,o<-b],x==t,all(elem b)[x,t],b==[i%i|i<-b]]where c=all(l>)(id=<<x);b=[0..l-1];a%b=x!!a!!b;l=length x;t=transpose x

Returns a list with five booleans, which are in order closure, associativity, commutativity, identity and idempotence.

Usage example: f [[1, 0, 0],[0, 1, 0],[0, 0, 1]] -> [True,False,True,False,False].

How it works:

f x=[
  c,                         -- closure (see below)
  c&&and[(m%n)%o==m%(n%o)|   -- assoc: make sure it's closed, then check the
          m<-b,n<-b,o<-b],   --        assoc rule for all possible combinations
  x==t,                      -- comm: x must equal it's transposition
  all(elem b)[x,t],          -- identity: b must be a row and a column
  b==[i%i|i<-b]              -- idemp: element at (i,i) must equal i
  ]
  where                      -- some helper functions
  c=all(l>)(id=<<x);         -- closure: all elements of the input must be < l 
  b=[0..l-1];                -- a list with the numbers from 0 to l-1
  a%b=x!!a!!b;               -- % is an access function for index (a,b)
  l=length x;                -- l is the number of rows of the input matrix
  t=transpose x

Edit @xnor found some bytes to save. Thanks!

Answer 3

CJam, 95 bytes

q~:Ae_A,:Bf<:*'**B3m*{_{A==}*\W%{Az==}*=}%:*'A*A_z='C*B{aB*ee_Wf%+{A==}f*B,2*='1*}%Ae_B)%B,='I*

Prints a subsequence of *AC1I. * is the symbol for closure, A is for associative, C is for commutative, 1 is for identity and I is for idempotent.

---

The input array is read q~ and stored in A (:A).

Closure

Ae_A,:Bf<:*'**

If all (:*) elements in the matrix (Ae_) are smaller f< than B=size(A) (A,:B), print a * ('**).

Associativity

B3m*{_{A==}*\W%{Az==}*=}%:*'A*

Generate all triples in the domain (B3m*). We print A if they all satisfy a condition ({...}%:*'A*).

The condition is that, for some triple [i j k], left-folding that list with A (_{A==}*) and left-folding its reverse [k j i] (\W%) with A^op ({Az==}*), the flipped version of A, are equal (=).

Commutativity

A must equal its transpose: A_z=. If so, we print C ('C=).

Identity

B{                         }%   For each element X in the domain (0..N-1):
  aB*                           Make N copies.
     ee                         [[0 X] [1 X] ...]
       _Wf%+                    [[0 X] [1 X] ... [X 0] [X 1] ...]
            {A==}f*             [A(0, X) A(1, X) ... A(X, 0) A(X, 1)]
                   B,2*=        This list should equal the domain list repeated twice.
                        '1*     If so, X is an identity: print a 1.

The identity is necessarily unique, so we can only print one 1.

Idempotent

Ae_B)%B,='I*

Check if the diagonal equals B,. If so, print an I.

Answer 4

Matlab, 226

a=input('');n=size(a,1);v=1:n;c=all(0<=a(:)&a(:)<n);A=c;for i=v;for j=v(1:n*c);for k=v(1:n*c);A=A&a(a(i,j)+1,k)==a(i,a(j,k)+1);end;end;b(i)=all(a(i,:)==v-1 & a(:,i)'==v-1);end;disp([c,A,~norm(a-a'),any(b),all(diag(a)'==v-1)])

An important thing to notice is that non-closed implies non-associative. Many of those properties can easily be checked using some properties of the matrix:

• Closure: All all matrix entries in the given range?
• Associativity: As always the most difficult one to check
• Commutativity: Is the matrix symmetric?
• Identity: Is there an index k such that the k-th row and k-th column are exactly the list of the indices?
• Idempotence: Does the diagonal correspond to the list of indices?

Input via standar Matlab notation: [a,b;c,d] or [[a,b];[c,d]] or [a b;c d] e.t.c.

Output is a vector of ones a zeros, 1 = true, 0 = false, for each of the properties in the given order.

Full code:

a=input('');
n=size(a,1);
v=1:n;
c=all(0<=a(:)&a(:)<n);               %check for closedness
A=c;
for i=v;
   for j=v(1:n*c); 
      for k=v(1:n*c);
          A=A&a(a(i,j)+1,k)==a(i,a(j,k)+1);   %check for associativity (only if closed)
      end;
   end;
   b(i)=all(a(i,:)==v-1 & a(:,i)'==v-1);      %check for commutativity
end
%closure, assoc, commut, identity, idempotence
disp([c,A,~norm(a-a'),any(b),all(diag(a)'==v-1)]);

Answer 5

JavaScript (ES6) 165

An anonymous function returning an array with five 0/1 values, which are in order Closure, Associativity, Commutativity, Identity and Idempotence.

q=>q.map((p,i)=>(p.map((v,j)=>(w=q[j][i],v-w?h=C=0:v-j?h=0:0,q[v]?A&=!q[v].some((v,k)=>v-q[i][q[j][k]]):A=K=0),h=1,p[i]-i?P=0:0),h?I=1:0),A=P=K=C=1,I=0)&&[K,A,C,I,P]

Less golfed

f=q=>(
  // A associativity, P idempotence, K closure, C commuativity
  // assumed true until proved false
  A=P=K=C=1, 
  I=0, // Identity assumed false until an identity element is found
  q.map((p,i)=> (
      h=1, // assume current i is identity until proved false
      p[i]-i? P=0 :0, // not idempotent if q[i][i]!=i for any i
      p.map((v,j)=> (
          w=q[j][i], // and v is q[i][j]
          v-w // check if q[j][i] != q[i][j]
          ? h=C=0 // if so, not commutative and i is not identity element too
          : v-j // else, check again for identity
            ? h=0 // i is not identity element if v!=j or w!=j
            : 0,
          q[v] // check if q[i][j] in domain
            ? A&=!q[v].some((v,k)=>v-q[i][q[j][k]]) // loop for associativity check
            : A=K=0 // q[i][j] out of domain, not close and not associative
        )
      ),
      h ? I=1 : 0 // if i is the identity element the identity = true
    )
  ),
  [K,A,C,I,P] // return all as an array
)

Test

f=q=>
  q.map((p,i)=>(
    p.map((v,j)=>(
      w=q[j][i],
      v-w?h=C=0:v-j?h=0:0,
      q[v]?A&=!q[v].some((v,k)=>v-q[i][q[j][k]]):A=K=0
    ),h=1,p[i]-i?P=0:0),
    h?I=1:0
  ),A=P=K=C=1,I=0)
  &&[K,A,C,I,P]

// test

console.log=x=>O.textContent+=x+'\n';

T=[
 [
  [[0, 1, 2, 3],
   [1, 1, 2, 3],
   [2, 2, 2, 3],
   [3, 3, 3, 3]]
 ,[1,1,1,1,1]] // has the properties of closure, associativity, commutativity, identity and idempotence.
,[ // exponentiation function on domain n=3:
  [[1, 0, 0],
   [1, 1, 1],
   [1, 2, 4]]
 ,[0,0,0,0,0]] // has none of the above properties.
,[ // addition function on domain n=3:
  [[0, 1, 2],
   [1, 2, 3],
   [2, 3, 4]] 
 ,[0,0,1,1,0]] // has the properties of commutativity and identity.
,[ // K combinator on domain n=3:
  [[0, 0, 0],
   [1, 1, 1],
   [2, 2, 2]]
 ,[1,1,0,0,1]] // has the properties of closure, associativity and idempotence.
,[ // absolute difference function on domain n=3:
  [[0, 1, 2],
   [1, 0, 1],
   [2, 1, 0]]
 ,[1,0,1,1,0]] // has the properties of closure, commutativity and identity.
,[ // average function, rounding towards even, on domain n=3:
  [[0, 0, 1],
   [0, 1, 2],
   [1, 2, 2]]
 ,[1,0,1,1,1]] // has the properties of closure, commutativity, identity and idempotence.
,[ // equality function on domain n=3:
  [[1, 0, 0],
   [0, 1, 0],
   [0, 0, 1]]
 ,[1,0,1,0,0]] // has the properties of closure, commutativity,
]  

T.forEach(t=>{
  F=t[0],X=t[1]+'',R=f(F)+'',console.log(F.join`\n`+'\n'+R+' (expected '+X+') '+(X==R?'OK\n':'Fail\n'))
  })

<pre id=O></pre>