# Properties of Binary Functions

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.

# 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

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!

• How about c=all(l>)? – xnor Dec 24 '15 at 7:28
• Also, [i%i|i<-b]==b. – xnor Dec 24 '15 at 7:34
• Very readable for code-golf - nice! – isaacg Dec 24 '15 at 9:26

# 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 Aop ({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.

# 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)]);

# 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>