Entropic matroids and their representation
Emmanuel Abbe Sophie Spirkl


A parametric model for wind turbine power curves incorporating environmental conditions
    [
    
=======================================================================================

This paper investigates entropic matroids, 
that is, matroids whose rank function is given as the Shannon entropy of random variables. In particular, we consider p-entropic matroids, for which the random variables each have support of cardinality p. We draw connections between such entropic matroids and secret-sharing matroids and show that entropic matroids are linear matroids when p=2,3 but not when p=9. Our results leave open the possibility for p-entropic matroids to be linear whenever p is prime, with particular cases proved here. Applications of entropic matroids to coding theory and cryptography are also discussed.





§ INTRODUCTION

Matroid theory generalizes the notion of independence and rank beyond vector spaces. In a graphical matroid, for example, the rank of a subset of edges is the size of an acyclic spanning set of edges; analogous to the rank of a subset of vectors, which is the size of a spanning set of linearly independent vectors. It is natural to ask whether such combinatorial structures can also be obtained from probabilistic notions of independence, based on random variables. In particular, the entropy can be used to measure dependencies between random variables and it can be used to define a matroid rank function as discussed below. One can then investigate how such entropic matroids relate to other matroids, in particular whether they admit linear representations as graphical matroids do. Before giving formal definitions of such entropic matroids, we give some general definitions for matroids.



 §.§ Definitions


We recall a few standard definitions related to matroids, see, for example, Oxley <cit.>. A matroid is a pair M=(E,r), where the ground set E is a finite set (typically E=[m], m ∈ℤ_+) and where the rank function r: 2^E →ℤ_+ satisfies 

  
  * For any A ⊆ E, r(A) ≤ |A| (normalization);
  
  * For any A ⊆ B ⊆ E, r(A) ≤ r(B) (monotonicity);
  
  * For any A, B ⊆ E, r(A ∪ B) + r(A ∩ B) ≤ r(A) + r(B) (submodularity). 


The submodularity property can be interpreted as a diminishing return property: for every A ⊆ B and x ∈ E, 

    r(A ∪ x) - r(A) ≥ r(B ∪ x) - r(B),

that is, the larger the set, the smaller the increase in rank when adding a new element. Independent sets in a matroid are the subsets S ⊆ E such that r(S)=|S| and maximal independent sets are called bases, whereas minimal dependent sets are called circuits.

A matroid M = (E,r) is linear if there is a vector space V and a map f: E → V such that r(S) = rank(f(S)) for all S ⊆ E, where rank denotes the rank function of V, that is, rank(f(S)) = dim span(f(S)). We say that a matroid is 𝔽-representable if in addition, V can be chosen as a vector space over the field 𝔽. 

Given a matroid M, a minor of M = (E, ℱ) is a matroid that can be obtained from M by a finite sequence of the following two operations: 

  
  * Restriction: Given A ⊆ E, we define the matroid M | A = (A, ℱ∩ 2^A).
  
  * Contraction: Given an independent set A ∈ℱ, we define the matroid M/A = (E∖ A, B ⊆ E∖ A: B ∪ A ∈ℱ). 
  

  We define the dual M^* = (E, r^*) of a matroid M = (E, r) is defined by letting r^*(A) = r(E ∖ A) + |A| - r(E) for all A ⊆ E. A matroid property is a dual property if M has the property if and only if M^* does.


Being an F-representable matroid is a dual property, thas is, M is F-representable if and only if M^* is. 




 §.§ Entropic Matroids


One may expect that matroids could also result from probabilistic structures. Perhaps the first possibility would be to define a matroid to be `probabilistic' if its elements can be represented by random variables (with a joint distribution on some domain), such that a subset S is independent if the random variables indexed by S are mutually independent. This, however, does not necessarily give a matroid. For example, let X_1 and X_2 be independent random variables (for example, normally distributed) and let X_3=X_1+X_2. Let A={3}, B={1,3} and x={2}. Then r(A ∪ x) - r(A)=0 since X_2 and X_3 are dependent but r(B ∪ x) - r(B)=1 since B ∪ x= {1,2,3} contains two independent random variables. So this violates the submodularity requirement.

On the other hand, it is well known that the entropy function satisfies the monotonicity and submodularity properties <cit.>. Namely, for a probability measure μ on a discrete set , the entropy of μ in base q is defined by 

    H(μ)   = - ∑_x ∈μ(x) log_qμ(x).


For two random variables X and Y with values in 𝒳 and 𝒴 respectively and with joint distribution μ, we define the conditional entropy 

    H(X|Y) 
    = ∑_x ∈𝒳, y ∈𝒴μ(x,y) logμ(x,y)/∑_u ∈μ(u,y).


In particular, we have the chain rule of entropy H(X|Y) = H(X,Y) - H(Y). 
We also define the Hamming distance of two vectors x and y as d(x,y) = |1 ≤ i ≤ n  x_i ≠ y_i| and  the Hamming ball of radius r around x as B_r(x) = y  d(x,y) ≤ r.

Furthermore, for a probability measure μ of m random variables defined each on a domain , that is, for a probability distribution μ on ^m, one can define the function 

    r(S) =H(μ_S),    S ⊆ [m],

where μ_S is the marginal of μ on S, that is, 

    μ_S (x[S])   =∑_x_i ∈ [q] : i ∉ S μ(x),    x[S]={x_i : i ∈ S}.


By choosing the base q for the entropy in (<ref>) to be ||, we also get that r(S) ≤ |S|, with equality for uniform measures.
Therefore, the above r satisfies the three axioms of a rank function, with the exception that r is not necessarily integral.
In fact this defines a polymatroid (and r is also called a β-function <cit.>) and entropic polymatroids (i.e., polymatroids derived from such entropic β-functions) have been studied extensively in the literature; see References <cit.> and references therein. Using the Shannon entropy to study matroid structures already emerged in the works <cit.>, where the family of pairs of sets (i,j) and K such that K ⊆ [m], i,j ∈ [m] ∖ K is called probabilistically representable if there exit random variables {X_k}_k ∈ [m] such that X_i and X_j are conditionally independent given X_K, with the latter expressed in terms of the Shannon entropy as r(i,K)+r(j,K)-r(i,j,K)-r(K)=0.

However, we can also investigate what happens if this function r is in fact integral. This is the object of study in this paper.

Let q ∈ℤ_+. A matroid M=([m],r) is q-entropic if there is a probability distribution μ on [q]^m such that for any S ⊆ [m],

    r(S)=H(μ_S),

where μ_S is the marginal of μ on S and H is the Shannon entropy in base q.

Note that the entropy does not depend on the support of the random variables but only on their joint distribution. For this reason, the restriction that μ is taking values in [q]^m is in fact equivalent to requiring that each random variable has a support of cardinality at most q. When working with the m underlying random variables X_1,…,X_m distributed according to μ, we write H(S)=H(X[S])=H(X_i: i ∈ S)=H(μ_S).

With the integrality constraint, the random variables representing a q-entropic matroid must be marginally either uniformly distributed or deterministic, each pair of random variables must be either independent or a deterministic function of each other, and so on. These represent therefore extremal dependencies. As discussed in Section <ref>, such distributions (with extremal dependencies) have recently emerged in the context of polarization theory and multi-user polar codes <cit.>, which has motivated in part this paper. In Section <ref>, we also comment on the connection between secret sharing from cryptography.  

It is well-known and easy to check that entropic matroids generalize linear matroids, see, for example, References <cit.>. For completeness we recall the proof, making explicit the dependency on the field size. 
 Let 𝔽 be a finite field. If a matroid is -representable then it is ||-entropic.


Let M be an 𝔽-representable matroid and A be a matrix in 𝔽^|E| × n whose rows correspond to elements of E so that a subset of rows is linearly independent in 𝔽^n if and only if the corresponding subset of E is independent in M. Let Y_1, …, Y_n be mutually independent and uniformly distributed random variables over 𝔽 and let Y = (Y_1, …, Y_n). Then the vector of random variables (X_1, …, X_|E|) = A · Y satisfies that for any B ⊆ E, H(X_i  i ∈ B) = rankA_i  i ∈ B. Thus the entropy function on X_1, …, X_|E| recovers the rank function of M and M is ||-entropic. 


Our main goal throughout the remainder of this paper is
to investigate whether entropic matroids are always representable over fields. As discussed in next section, we will approach this question by checking whether the forbidden minors of representable matroids are
entropic or not. This strategy is justified by the fact that for the
Shannon entropy, entropic matroids are a minor-closed class, as we
will show in Lemma <ref>.



 §.§ Results

We prove that for every p, a matroid is p-entropic if and only if it is secret-sharing with a ground set of size p, which is equivalent to being the matroid of an almost affine code with alphabet size p. Furthermore, we prove that for every p, being p-entropic is closed under taking matroid minors. 

We give alternative proofs that for p=2 and p=3, being p-entropic is equivalent to being 𝔽_p-representable by examining known forbidden minor characterizations. We also make some partial progress towards proving the same for other primes p. In the final section of the paper, we mention some applications of entropic matroids in coding. 



§ FURTHER RELATED LITERATURE

Matroid representations and forbidden minors were studied in Reference <cit.> for GF(3), Reference <cit.> for GF(4) and some results for general fields were obtained in References <cit.>. Linear representable matroids are also intimately related to linear solutions to network coding problems, in particular in Reference <cit.>, in which a network-constrained
matroid enumeration algorithm is developed, as well as Reference <cit.> that considers integer-valued polymatroids and   representable polymatroids in References <cit.>. Matroid’s minors and the connection to Zhang-Yeung inequality was discussed in Reference <cit.>, which shows in particular that almost entropic matroids have infinitely many excluded minor. Matroids, secret sharing and linearity are also discussed in several papers as mentioned in part earlier. Reference <cit.> gave the first example of an access structure (i.e., the parties that can recover the secret from their share) induced by a matroid, namely the Vamos matroid, that is non-ideal (a measure of optimality of the secret shares lengths); Reference <cit.> presented the first non-trivial lower bounds on the size of the domain of the shares for secret-sharing schemes realizing an access structure induced by the Vamos matroid and this is later improved in Reference <cit.> using using non-Shannon inequalities for the entropy function. As mentioned earlier, an important line of work is also dedicated to understanding the representation of entropic polymatroids for a fixed ground set cardinality <cit.>, which is well-understood for cardinality 2 and 3 and more complicated for larger cardinality with the non-Shannon inequalities emerging. 







§ MINORS OF ENTROPIC MATROIDS


In this section, we prove the following: 

 
  Let M be an entropic matroid on random variables X_1, …, X_m
  with values in 𝔽_p and with entropy H and joint
  distribution μ.
  
  
  (i) For any A ⊆X_1, …, X_m, M|A is
    entropic.
  
  (ii) For any X_i ∈X_1, …, X_m with H(X_i)=1, M/X_i is
    entropic.
  
  (iii) For any independent set A, M/A is
    entropic.
  


  For each of the claims, we construct random variables and a probability distribution whose entropy agrees with the rank function of the matroid in question.
  
  To prove (i), we consider the variable set A with the marginal
  distribution given by μ. Then H is integral on any subset of A, since it is integral on any subset of X_1, …, X_m. This implies (i). 

  To prove (ii), we consider two cases. If for any B ⊆X_1, …, X_m with X_i ∉B we have H(X_i, B) =
  H(B)+1, then X_i is independent of all other variables. In
  particular, any set is independent in M if any only if its union
  with X_i is. Therefore, M/X_i = M|X_1, …,
    X_i-1, X_i+1, …, X_m in this case and the result follows
  from (i). 

  Otherwise, we define a distribution on
  X_1, …, X_i-1, X_i+1, …, X_m by fixing any
  value x for X_i with X_i = x > 0 and considering the
  probability distribution obtained by conditioning on the event
  {X_i = x}.  Now let A ⊆X_1, …, X_i-1, X_i+1, …, X_m. There   are two cases. If there is no circuit C with X_i ∈ C such that   A contains C ∖X_i as a subset, then 
  H(A) + 1 = H(A, X_i) = H(A) + H(X_i | A), therefore
  H(X_i | A) = 1 and so X_i and A are independent. In this case,
  H(A | X_i = x) = H(A), thus H agrees with the rank function of
  M/X_i.

  If adding X_i to A creates a circuit, then H(A,X_i) = H(A) and 
  H(A|X_i) = H(A)-1. Let X(A) denote the vector with
  components X_j, j ∈ A and let 𝒴 = 𝔽_p^A denote the
  set of possible values of X(A). 

  Suppose first that H(A|X_i = k) < H(A) - 1 for some k ∈𝔽. Now let B be a basis
  in A, that is, |B| = H(B) = H(A). We have that H(A|X_i=k)=H(B|X_i=k)
  + H(A|B,X_i=k) and H(A|B, X_i=k) ≤ H(A,X_i|B) = H(A|B) =
  0. Therefore, H(B|X_i=k) < |B|-1.
  
  Now let C be the unique circuit in B ∪{i}. It follows that H(C) = H(C∖X_i) = |C|-1 and
  H(B∖ C|C) = H(B)-H(C) = |B∖ C|. In particular, the
  variables in B∖ C are independent of X_i in the marginal
  distribution on B and thus 
    H(B|X_i = k) = H(B∖ C) + H(C
      ∖X_i| X_i=k, B ∖ C) = |B∖ C| + H(C |
      X_i=k).
 
  
  This implies that H(C|X_i=k) < |B| - |B∖ C| - 1 = |C|
  -2. But X_i = k | X(C∖X) = c∈0,1
  and X(C∖X_i) = c = p^-|C|+1, which implies
  that X(C)=c∈0, p^-|C|+1 and X(C∖X_i) = c | X_i = k∈0, p^-|C|+2. Since these
  probabilities add up to one, it follows that exactly p^|C|-2 of them are
  non-zero, which yields

    H(C|X_i=k)    = ∑_cX(C∖X_i)=c | X_i=klog_p (1/X(C∖X_i)=c | X_i=k). 
       = p^|C|-2( p^-|C|+2log_p (1/p^-|C|+2)) 
       = |C| -2,

a contradiction to the assumption H(C) < |C|-2. 

This implies that H(A|X_i = k) ≥ H(A) - 1 for all A. Since

    H(A) - 1    = H(A|X_i) = ∑_k=0^p-1X_i = kH(A|X_i = k) 
       = ∑_k=0^p-11/p H(A|X_i = k) ≥ p ·1/p (H(A)-1) = H(A)-1,

 it follows that we have H(A|X_i = k) = H(A) - 1 for all summands. This implies that the entropy of the conditional distribution yields the entropic matroid M/X_i and this proves (ii). 

Finally, (iii) follows by applying (ii) repeatedly. 


This lemma proves that the property of being an entropic matroid is closed under taking minors. This means that in order to show entropic matroids belong to a minor-closed class of matroids, it suffices to show that the forbidden minors of this class are not entropic.



§ SECRET-SHARING AND ALMOST AFFINE MATROIDS



Secret-sharing matroids were introduced in Reference <cit.>. These matroids are motivated by the problem of secret-sharing in cryptography <cit.>, which refers to distributing a secret among a collection of parties via secret shares such that the secret can be reconstructed by combining a sufficient number (of possibly different types) of secrete shares, while individual shares being of no use on their own.

We use the following definitions from Reference <cit.>: 
Let A ∈ S^I × E be a matrix, where S, I and E are finite sets. For i ∈ I, e ∈ E and Y ⊆ E ∖e,
we define n(i, e, Y ) = a_je j ∈ I, a_jy = a_iy for all y ∈ Y. Then A is a secret-sharing matrix if
for e ∈ E and Y ⊆ E ∖e, either n(i, e, Y ) = S for all i ∈ I or |n(i, e, Y )| = 1 for all
i ∈ I. Any secret-sharing matrix induces a secret-sharing matroid with ground set E and rank
function r(Y ) the logarithm with base |S| of the number of distinct rows of the submatrix
A[Y ] = (a_ij i ∈ I, j ∈ Y ) of A. In particular, Y is independent if and only if A[Y ] contains all
vectors in S^Y.

The interpretation is as follows. Suppose some row i ∈ I has been chosen in A but its value has been kept secret. Knowing A, one wishes to determine as much as possible about the values a_ie, e ∈ E, without knowing which row has been selected. If by some means one has been able to determine the values a_if
for all f ∈ Y ⊆ E. Then the possible values of a_ie for some e ∈ E ∖ Y, consistent with the available information, are precisely the members of n(i, e, Y) (and
this set can be determined despite not knowing i). 


Secret-sharing matroids were connected to entropy rank functions in Reference <cit.>, as further discussed below. 
We now formally connect the two classes of matroids. 
  
If a matroid is p-entropic, then it is a secret-sharing matroid with a ground set of size p. 


  Given a p-entropic matroid M with ground set E and rank
  (entropy) function H, we let A be the matrix containing all vectors
  in ℤ^E_p which correspond to outcomes of positive
  probability in M. For every set Y of variables, A[Y ] contains the
  possible outcomes of these variables. These outcomes are all equally
  likely and the number of distinct outcomes with positive
  probability is p^H(Y ). This implies that to prove that M is a secret-sharing matroid, it suffices to prove that A is a secret-sharing matrix.

  Let e ∈ E and Y ⊆ E ∖e. Then n(i, e,
  Y ) is the number of possible values of the random variable X_e
  ∈ E associated with e when Y is fixed to its values in
  outcome i. But H(X_e|Y ) ∈0, 1 and if H(X_e|Y ) = 0
  then X_e is determined by the values of Y and |n(i, e, Y )| =
  1 for all i; if H(X_e|Y ) = 1 then X_e is independent of the
  values of the variables in Y and thus n(i, e, Y ) =
  ℤ_p. This proves that A is a secret-sharing matrix.


Note that this proof remains true for any p ∈ℕ_≥ 1,
that is, it does not require the ground set to be a field. The
converse of Lemma <ref> is true as well: every
secret-sharing matroid is p-entropic for some p. This was observed
in Reference <cit.> and we include a proof for completeness. Together, this observation and Lemma <ref> provide an
alternative characterization of entropic matroids as secret-sharing matroids.

 Every secret-sharing matroid with ground set S is |S|-entropic.

 Let M be a secret-sharing matroid and A a
  secret-sharing matrix inducing M. Without loss of generality, we
  may assume that A does not contain two identical rows, since this
  does not affect the structure of the matroid. The definition of
  secret-sharing matroids implies that the number of rows of A is a power
  |S|^r of |S|. We define a probability distribution on the set of
  random variables X_e : e ∈ E by setting the probability that (X_e)_e ∈ E = a as |S|^-r for every row a of A. 

  We proceed by induction on |E∖ Y| to show that H(Y ) (with the Shannon
  entropy with base |S|) is integral for every Y ⊆ E and
  moreover, that the resulting probability distribution on Y is the
  uniform distribution on the distinct rows of A[Y ]. This is
  clearly true for Y = E, since H(E) = r. Let Y ⊂ E and
  let e ∈ E ∖ Y , then by the induction hypothesis, H(Y ∪e) = k ∈ℕ.  The matrix A[Y ∪e] has
  |S|^k distinct rows and each distinct row has the same
  probability |S|^-k.  If H(X_e|Y ) = 0, then H(Y ) = k and
  distinct rows in A[Y ∪e] are distinct rows of A[Y ] and
  thus the distribution of the variables in Y is the same as for the
  variables of Y ∪e. Therefore, we may assume that fixing
  the values of the variables in Y does not always determine
  X_e. This means that n(i, e, Y ) = |S| for all i. In   particular, every distinct row of A[Y ] gives rise to |S| distinct rows
  in A[Y ∪e] and thus A[Y ] has |S|^k-1 distinct
  rows. Each distinct row has the same multiplicity |S|^r-k in
  A[Y ∪e] by the induction hypothesis and thus each distinct row
  of A[Y ] has multiplicity |S|^r-k+1. Now the resulting distribution of the variables in Y is a uniform distribution with |S|^k-1
  distinct outcomes, therefore H(Y ) = k - 1. Clearly, r_M(Y ) = k - 1 and
  therefore this induction allows us to conclude that the rank in M
  coincides with the entropy of the constructed distribution. This
  implies the result. 


Seymour <cit.> proved that the Vamos matroid is not a secret sharing matroid. This implies that it is not an entropic matroid for any p. 

Moreover, there is a secret-sharing matroid which is not
representable over the corresponding field (with |S| elements) and
which has been discovered by Simonis and Ashikhmin <cit.>. This example is the non-Pappus matroid, shown
in Figure <ref>. This matroid has nine elements
1, … , 9 as its ground set E and each X ⊆ E has
rank min(|X|, 3) with the exception of the eight 3-elements sets shown
as colored lines, which each have rank 2. Pappus' theorem proves that
this matroid is not representable over any field. 

The non-Pappus matroid.0.4non-pappus

Simonis and Ashikhmin <cit.> show that
the row space of the matrix 

    [ 10 10 00 10 00 10 10 10 00; 01 01 00 01 00 01 01 01 00; 00 00 00 10 10 21 01 10 10; 00 00 00 02 01 20 12 02 01; 00 10 10 01 00 01 00 11 10; 00 01 01 21 00 21 00 10 01;    ]

is a secret-sharing matrix, where each entry of the matrix is
considered as an element of 𝔽^2_3.  They introduce another
definition of entropic matroids via codes: a code (subset)
𝒞⊆ S^E is almost affine if r(Y ) :=
log_|S| (|𝒞_Y |) ∈ℕ_0 for all Y ⊆ E,
where 𝒞_Y denotes the projection of 𝒞 to the
variables in Y. The corresponding matroid M with ground set E and
rank function r is called an almost affine matroid. It is not hard to
see that this definition coincides with secret-sharing matroids by
using the codewords in C as the rows of the secret-sharing matrix A
and vice versa. These results show that not all entropic matroids are
representable by giving a 9-entropic matroid which is not
representable over any field.



§ THE CASE P=2

An 𝔽_2-representable matroid is called binary. The goal of this section is to prove the following. 

Every 2-entropic matroid is binary.

To prove this, we use the characterization of binary matroids proved by Tutte <cit.> stating that a matroid is binary if and only if it has no U_2,4-minor. U_2,4 is the uniform matroid of rank two on four elements: E = [4] and ℱ consists of all subsets of E of cardinality at most two. Using Tutte's characterization, the theorem follows from the next lemma. 

U_2,4 is not 2-entropic.


  Suppose for a contradiction that μ is a probability distribution on four random variables X_1, …, X_4 whose entropy is the rank function of U_2,4, then H(X_i) = 1 for all i and H(X_i, X_j) = 2 for all i≠ j; furthermore H(X_1, X_2, X_3, X_4) = 2. This implies that X_i = a, X_j = b = 1/4 for all i ≠ j and a, b ∈𝔽_2, because the marginal distribution of X_i and X_j has to be the product of two independent (1/2) distributions to achieve an entropy of two.

Furthermore, H(X_i, X_j | X_k, X_l) = 0 for i,j,k,l = [4] by the chain rule and therefore X_1 = a, X_2 = b, X_3 = c, X_4 = d∈0, 1/4 for all a, b, c, d. Without loss of generality, we may assume that X_1 = 0, X_2 = 0, X_3 = 0, X_4 = 0 = 1/4 but then every other event in which at least two different variables X_i and X_j are zero must have probability zero, since X_i = 0, X_j = 0 = 1/4. Since X_i = 0, X_j = 1 = 1/4, it follows that all outcomes with three ones have probability 1/4. Now 1/4 = X_1 = 1, X_2 = 1≥X_1 = 1, X_2 = 1, X_3 = 0, X_4 = 1 + X_1 = 1, X_2 = 1, X_3 = 1, X_4 = 0 = 1/2, a contradiction. 





§ THE CASE P=3

An 𝔽_3-representable matroid is called ternary. The following structure theorem has been proved independently by Seymour <cit.> and Bixby <cit.>, who attributed it to Reid. 


A matroid is ternary if and only if it contains no minor isomorphic to U_2,5, U_3,5, the Fano plane F_7 or its dual. 




The Fano plane, shown in Figure <ref>, has a ground set E=[7] and can be represented over 𝔽_2 by the column vectors of the matrix
[ 1 1 0 0 0 1 1; 1 0 1 0 1 0 1; 1 0 0 1 1 1 0 ], that is, a set is independent if and only if it contains at most three vectors and it does not contain all three vectors on any line (including the circle). 

The Fano plane.0.45fano-plane

 U_2,5 is not 3-entropic.


Suppose for a contradiction that there exist X = (X_1, …, X_5) such that H(A) = min|A|,2 for all A ⊆X_1, …, X_5. Then, for any choice of a,b,c,d,e = 1,2,3,4,5, we have that H(X_a, X_b, X_c | X_d, X_e) = 0 and thus for any vector x ∈𝔽_3^5, 
    X_a = x_a, X_b = x_b, X_c = x_c | X_d = x_d, X_e = x_e∈0,1
 and X = x∈0, 1/9. 

As in the proof for U_2,4, we may assume that X = 0 = 1/9 but then any other event with at least two zeros must have probability 0. This leaves six events, five with one zero and one with no zeros; but each of them has probability at most 1/9, thus the total probabilities add up to at most 7/9, a contradiction. 


 U_3,5 is not 3-entropic.

 
  As before, we suppose for a contradiction that there is a vector X = (X_1, …, X_5) of random variables such that H(A) = min|A|,3 for all A ⊆X_1, …, X_5.

  Every three distinct variables are independent and they determine the other two variables. It follows that, for every event, its probability is either zero or 1/27. But there are only 81 outcomes and 27 of them occur with positive probability. Each of those 27 must differ from the others in at least three places, because if two outcomes are equal in three positions, the other two are determined and thus equal. This means that the Hamming balls of radius 1 around the outcomes with positive probability are disjoint. Each of these Hamming balls contains 11 elements: the outcome with positive probability and the outcomes in which one variable is flipped to one of the two other possible values. Therefore, we have at least 27 · 11 = 297 outcomes, a contradiction. 


 The Fano plane is not 3-entropic.

 Suppose for a contradiction that the Fano plane is 3-entropic and that X = X_1, …, X_7 is a set of random variables whose entropy corresponds to their rank in the Fano matroid as shown in Figure <ref>. Since the maximum size of an independent set in the Fano matroid is three, any three independent variables determine the values of all the others; in particular, there are at most 27 outcomes with positive probability, which we denote by their values on the independent set X_1, X_2, X_3. Since H(X_1, X_2, X_3) = 3, each of these outcomes has probability 1/27, whereas all other outcomes have probability zero. It follows that we have a map f 𝔽_3^3 →𝔽_3^4 mapping the values on X_1, X_2, X_3 to the values on X_4, …, X_7, where X_2 and X_3 determine X_7, X_1 and X_2 determine X_5 and X_3 and X_1 determine X_6 but every change of one of X_1, X_2, X_3 must change X_4. 

We consider the set of nine assignments of X_1, X_2, X_3 for which X_4 = 0. If every two of these have pairwise distance at least three, we can only have three distinct assignments. This implies that we may assume that there are two assignments with distance two. Furthermore, if we fix any two digits, exactly one choice is valid for the remaining digit. Therefore, up to isomorphism (exchanging symbols), the set looks as follows: 000, 012, 021, 102, 111, 120, 201, 210, 222; and thus X_4 = X_1 + X_2 + X_3. 

The random variables X_2, X_3, X_4 determine X_5, X_6, X_7 and
X_1. In particular, both of the pairs X_1, X_1 + X_2 + X_3 and
X_2, X_3 determine X_7. 

Changing X_1 does not change X_7 and neither does simultaneously
adding k to X_2 and subtracting k from X_3. Therefore, keeping X_2
+ X_3 constant will keep X_7 constant and H(X_7 | X_2 + X_3) = 0,
and H(X_2 + X_3 | X_7) = 0. This implies that there is a one-to-one correspondence between X_7 and X_2 + X_3 and similarly between X_6 and X_2 + X_4 and between X_5 and X_3 + X_4. But then X_5, X_6, X_7 allow us to find X_2 + X_3, X_2 + X_4 and X_3 + X_4 and thus 2X_2 + 2X_3 + 2X_4 and X_2 + X_3 + X_4 (since 2 ≠ 0 in 𝔽_3), which is X_1. This shows that H(X_1 | X_5, X_6, X_7) = 0 and thus 3 = H(X_1, X_5, X_6, X_7) = H(X_5, X_6, X_7) = 2, a contradiction.
 
The above proof actually shows that the Fano plane is not p-entropic for any p > 2, which gives an alternative proof that it is not 𝔽_p-representable for p>2 either. 

The dual F_7^* of the Fano plane is 𝔽_2-representable and a representation is given by the columns of the matrix 
[ 1 1 1 1 1 1 1; 1 1 0 0 0 1 1; 1 0 1 0 1 0 1; 1 0 0 1 1 1 0 ]. This shows that every 3-element set is independent in F_7^*, thus its circuits are exactly the complements of the three-element circuits of the Fano plane. To give a better understanding of these matroids, we expanded the symmetrical representation of F_7 given in Reference <cit.> and shown in Figure <ref>a to F_7^*. The result is shown in Figure <ref>b. Each color connects the elements of a circuit in one figure and the corresponding circuit given by its complement in the other figure. The cyclical order of the nodes in Figure <ref>a yields a rainbow Hamilton cycle (one edge of each color) in Figure <ref>.



The dual of the Fano plane is not 3-entropic. 



  Suppose for a contradiction that X = (X_1, …, X_7) is a vector of random variables whose entropy coincides with the rank function of F_7^*. Since H(X_2, X_3, X_4, X_5) = 4 and H(X) = 4, X = x∈0, 1/81 for all x ∈𝔽_3^7. We refer to the events with positive probability as outcomes. 

By permuting the symbols, we may assume that 0000000 is a possible outcome. We consider the other outcomes (X_1, X_6, X_7) for X_2 = 0. No two of these outcomes can have distance one, because X_1, X_2, X_6, X_7 is a cycle, so for fixed X_2, any two distinct possible outcomes must have distance at least two on their restriction to (X_1, X_6, X_7). In the proof of the previous lemma, we have already to shown that by switching digits, we may assume that the set of images is 000, 012, 021, 102, 111, 120, 201, 210, 222. As shown in Figure <ref>, this also determines the other two sets (but not necessarily which of them is which). This shows that X_1 + X_6 + X_7 is sufficient to determine X_2 and vice versa; by flipping symbols 1 and 2 for X_2, we may assume that X_1 + X_6 + X_7 = X_2. 

Values of (X_1, X_6, X_7) colored by corresponding value of X_2.0.45cube

We now fix X_3. Then X_4 is determined by either X_1, X_2=X_1 + X_6 + X_7 or X_6, X_7 and thus changing X_1 or adding k to X_6 and subtracting it from X_7 does not change X_4. This implies that X_4 depends only on X_6 + X_7 (and X_3) and thus H(X_3, X_4, X_6 + X_7) = 2. Analogously, H(X_3, X_5, X_1 + X_7) = 2 and H(X_4, X_5, X_1 + X_6) = 2. Therefore, X_3, X_4 and X_5 determine X_6 + X_7 + X_1 + X_7 + X_1 + X_6 = 2 (X_1 + X_6 + X_7) = 2 X_2 and since 2 ≠ 0 in 𝔽_3, this shows that H(X_2, X_3, X_4, X_5) = 3, contradicting the assumption that X had the entropy function given by the rank in F_7^*.  


Combining these four lemmas with the characterization of ternary matroids, we have proved the following theorem (the interesting part being the only if part).

A matroid is 3-entropic if and only if it is 𝔽_3-representable. 



§ COMMENTS FOR GENERAL PRIMES P

For ground sets of arbitrary size p, being p-representable is a
stronger assumption than being p-entropic as the example of Simonis
and Ashikhmin <cit.> of the non-Pappus matroid (see
Figure <ref>) shows. However, no counterexamples exist
in the case where the ground set has prime order.  

In this section, we show that for primes p, every p-entropic
matroid of rank at most two is linear, that is, let M be an entropic
matroid with ground set E and H(E) ≤ 2, then M is linear.  If
H(E) < 2, this is true since any basis has at most one
element. Furthermore, we may assume that every X ∈ E satisfies
H(X) = 1, for otherwise X is deterministic and is represented by the zero vector in every linear representation. 


  Let M be a p-entropic matroid of rank 2. If there are two
  elements X and Y in the ground set E with H(X, Y ) = 1, then
  M is 𝔽_p-linear if and only if M ∖X is.


  If M is 𝔽_p-representable, then so is M ∖X,
  since it is a minor-closed property. Suppose that M ∖X is
  representable and let f  E ∖X→ V be
  a representation and let g  E → V be defined as
  f(Z) for Z ≠ X and f(X) = f(Y ). Let S ⊆ E. Then
  ((g(S))) = H(S) for X ∉E. If X ∈ S but Y
  ∉S, then ((g(S))) = ((f(S ∪Y
  ))) = H(S ∪Y ) and 
  
    H(S ∪Y )    = H(S) + H(Y |S) 
       = H(S) + H(X|S) + H(X, Y |S) - H(X|S) + H(Y |S) - H(X, Y |S) 
       = H(S) + H(X|S) + H(Y |X, S) - H(X|Y, S) = H(S ∪X).

 
  If X, Y ∈ S, then ((g(S))) = ((f(S∖X))) = H(S∖X) = H(S) by applying
  submodularity to the sets X, Y and
  S∖X. This proves that g is an
  𝔽_p-representation of M.


With the above lemma, we have reduced the problem to considering uniform matroids. For any prime p, the uniform matroid U_2,p+1 is
𝔽_p-representable by choosing the images of E as 
    (0,
    1),(1, 0),(1, 1),(1, 2), … ,(1, p - 1) ∈𝔽_p^2.
 

Each
pair of these p + 1 vectors is independent and a basis of
𝔽^2_p, thus they represent U_2,p+1.  The following
lemma shows that any larger uniform matroid is neither p-entropic nor
𝔽^2_p-representable.

 The uniform matroid U_2,p+2 is not p-entropic for
  any p ∈ℕ_≥ 2.
 

  Suppose not and let C denote the set of possible outcomes
  for a probability distribution on p + 2 variables representing
  U_2,p+2. By changing symbols, we may assume that (0, …, 0)
  is a possible outcome. Furthermore, there are p^2 outcomes and hence
  p of them begin with a zero. These p outcomes have the same
  value at the first coordinate X_1 but all other values are
  distinct (i.e., each X_i for i > 1 takes all of its p possible
  values exactly once among these p outcomes, including value zero
  for outcome (0, …, 0)).  Therefore, we can simultaneously
  change the other symbols so that these p outcomes become (0, 0,
  …, 0),(0, 1, …, 1),(0, 2, …, 2), … ,(0, p-1, …,
  p-1). But then any other outcome not starting with zero satisfies that X_2, …, X_p+2 all take different values in
  ℤ_p. Since there are only p values but p + 1
  variables, this is a contradiction.


This shows that line matroids, which are among the forbidden minors of
binary and ternary matroids, are p-entropic if and only if they are
𝔽_p-linear.



§ APPLICATION: ENTROPIC MATROIDS IN CODING

We recall here a result proved in Reference  <cit.> that makes entropic matroids emerge in a probabilistic context and which gives further motivations to studying entropic matroids. 
The result gives in particular a rate-optimal code for compressing correlated sources, similarly to the  channel counter-part developed in Reference <cit.>. 

Let X^n=(X_1,…,X_n) be an i.i.d. sequence of discrete random variables taking values in ^m.
That is, X^n is an m × n random matrix with i.i.d. columns of distribution μ on ^m. 
One can assume that the support of  is finite (countable supports can be handled with truncation arguments) and to further simplify, we assume that  is binary, associating each element in the binary field, that is, =GF(2). 

Due to the i.i.d. nature of the sequence, the entropy of X^n is the sum of each components' entropies H(μ), i.e., 

    H(X^n)=nH(μ).


The next result shows that it is possible to transform the sequence X^n with an invertible map that extracts the entropy in subsets of the components. In words, the transformation takes the i.i.d. vectors under an arbitrary μ to a sequence of distributions that correspond in the limit to entropic matroids. 


Let m be a positive integer, n be a power of 2 and X^n be an m × n random matrix with i.i.d. columns of distribution μ on _2^m.
Let Y^n=X^n G_n over _2, where G_n=[[ 1 0; 1 1;   ]]^⊗log_2(n). For any =O(2^-n^β), β < 1/2, we have 

    |{i ∈ [n] :  H(Y_i[S]|Y^i-1) ∉±,  for any  S ⊆ [m] }| = o(n).


In other words, one starts with an i.i.d.  sequence of random vectors under a distribution μ that defines an entropic polymatroid [m] ⊇ S ↦  H(S) and after the transformation G_n, one obtains a sequence of random vectors which is no longer i.i.d. but where each random vector given the past defines an entropic matroid in the limit. Having a matroid structure is of course much easier to handle for compression purposes, one simply has to pick a basis for each matroid, store the components in that basis and the other components are fully dependent on these so they can be recovered without being stored. Of course, in practice n is large but finite, and each random vector defines  a polymatroid that is close to a matroid but a continuity argument allows to show that the components outside of the bases can still be recovered but only with high probability. Since a compression code is allowed to fail with a low probability of error, this is not an issue. Understanding the structure of these entropic matroids allows then one to better understand how the stored components can be allocated over the different components—see Reference <cit.> for further details. 


 



§ ACKNOWLEDGEMENTS


This research was partly funded by NSF grant CIF-1706648.

999

oxley Oxley, J.G. Matroid Theory; Oxford University Press: Oxford, UK, 2006; Volume 3.

woodall Woodall, D.R. Matroid Theory: Types of Matroids Lecture Notes.  Available online: <https://www.maths.nottingham.ac.uk/personal/drw/PG/matroid.ch3.pdf>.

fuji
Fujishije, S. Polymatroidal dependence structure of a set of random variables. Inf. Control 1978, 39, 55–72. 


lovasz
Lovász, L. Submodular functions and convexity. In Mathematical
Programming-The State of the Art; Bachem, A., Grötschel, M., Korte, B., Eds.; Springer: Berlin, Germany, 1982; pp. 234–257.


edmonds
Edmonds, J. Submodular Functions, Matroids and Certain Polyhedra; Lecture Notes in Computer Science; Springer: Berlin, Germany, 2003.

han
Han, T.S. A uniqueness of shannon's information distance and
related nonnegativity problems. J. Comb. Inf. Syst. Sci. 1981, 6, 320–331.

li Li, C.; Walsh, J.M.; Weber, S. Matroid bounds on the region of en- tropic vectors. In Proceedings of the 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA, 2–4 October 2013; pp. 796–803.



yeung
Zhang, Z.; Yeung, R. On characterization of entropy
function via information inequalities. IEEE Trans. Inf. Theory 1998, 44, 1140–1452.

yeung2 Yeung, R.W.
Information Theory and Network Coding; Springer: Berlin, Germany, 2008.

matus3
 Matús̆, F. On Equivalence of Markov Properties over Undirected Graphs. 
J. Appl. Probab. 1992, 29, 745–749.

matus1
 Matús̆, F. Probabilistic conditional independence structures and matroid theory: Background. Int. J. Gen. Syst. 1994, 22, 185–196.
 
 
 corr Abbe, E. Randomness and dependencies extraction via polarization, with applications to Slepian-Wolf coding and secrecy.
IEEE Trans. Inf. Theory 2015, 61, 2388–2398.

abbe_arxiv Abbe, E. Mutual information, matroids and extremal dependencies. arXiv 2010, arXiv:1012.4755. 

mat1 Kahn, J.; Seymour, P. On forbidden minors for GF(3). Proc. Am. Math. Soc. 1988, 102, 437–440.

mat3 Geelen, J.F.; Gerards, A.; Kapoor, A. The excluded minors for GF(4)-representable matroids. J. Comb. Theory Ser. B 2000, 79, 247–299.

mat2 Kahn, J. On the uniqueness of matroid representations over GF(4). Bull. Lond. Math. Soc. 1988, 20, 5–10.

mat4 Kung, J.P.; Oxley, J.G. Combinatorial geometries representable over GF(3) and GF(q). ii. dowling geometries. Gr. Comb. 1988, 4, 323–332.

mat5 Kung, J.P. Combinatorial geometries representable over GF(3) and GF(q). i. the number of points. Discret. Comput. Geom. 1990, 5, 83–95. 

mat6 Whittle, G. On matroids representable over GF(3) and other fields. Trans. Am. Math. Soc. 1997, 349, 579–603.

net1 Apte, J.; Li, C.; Walsh, J.M. Algorithms for computing network coding rate regions via single element extensions of matroids. In Proceedings of the 2014 IEEE International Symposium on Information Theory,  Honolulu, HI, USA , 29 June–4 July 2014; pp. 2306–2310.

net2 Salimi, A.; Médard, M.; Cui, S. On the representability of integer poly- matroids: Applications in linear code construction. In Proceedings of the 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Aller- ton), Monticello, IL, USA, 29 September–2 October 2015; pp. 504–508.

net3 Chan, T.; Grant, A.; Kern, D. Existence of new inequalities for repre- sentable polymatroids. In Proceedings of the 2010 IEEE International Symposium on Information Theory, Austin, TX, USA, 13–18 June 2010; pp. 1364–1368.

net4 Chan, T.; Grant, A.; Pfluger, D. Truncation technique for charac- terizing linear polymatroids. IEEE Trans. Inf. Theory 2011, 57, 6364–6378.

matus4
Matús̆, F. Classes of matroids closed under minors and principal extensions. Combinatorica 2018, 38, 935–954.

seymour2 Seymour, P. On secret-sharing matroids. J. Comb. Theory Ser. B 1992, 56, 69–73.

beimel
Beimel, A.; Livne, N.; Padro, C. Matroids can be far from ideal secret sharing. In Theory of Cryptography Conference; Springer: Berlin/Heidelberg, Germany, 2008; pp. 194–212.

martin Martin, S.; Padro, C.; Yang, A. Secret sharing, rank inequalities, and information inequalities. IEEE Trans. Inf. Theory 2015, 62, 599–609.

bd Brickell, E.F.; Daniel, M.D. On the classification of ideal secret sharing schemes. J. Cryptol. 1991, 4, 123–134.

secret1
Blakley, G.R. Safeguarding Cryptographic Keys. In Proceedings of the 1979 AFIPS National Computer Conference, Monval, NJ, USA, 1979; Volume 48, pp. 313–317.

secret2
 Shamir, A. How to share a secret. Commun. ACM 1979, 22, 612–613.

mfp Martí-Farré, J.; Padró, C. On secret sharing schemes, matroids and polymatroids. In Theory of Cryptography Conference; Springer: Berlin/Heidelberg, Germany, 2007; pp. 273–290.

simonis Simonis, J.; Alexei, A. Almost affine codes. Des. Codes Cryptogr. 1998, 14, 179–197.

tutte Tutte, W.T. A homotopy theorem for matroids II. Trans. Am. Math. Soc. 1958, 88, 144–174.

seymour Seymour, P. Matroid representation over GF(3). J. Comb. Theory Ser. B 1979, 26, 159–173.

bixby Bixby, R.E. On Reid's characterization of the ternary matroids. J. Comb. Theory Ser. B 1979, 26, 174–204.

pegg Pegg Jr., E. Math Games: The Fano Plane. Available online: <http://www.mathpuzzle.com/MAA/47-Fano/mathgames_05_30_06.html>. 

mac Abbe, E.; Telatar, E. Polar codes for the m-user multiple access channel.
IEEE Trans. Inf. Theory 2012, 58, 5437–5448.


