13
$\begingroup$

Over at PPCG there is an ongoing contest going on to find the largest matrix without a certain property, called property $X$. The description is as follows (copied from the question).

A circulant matrix is fully specified by its first row $r$. The remaining rows are each cyclic permutations of the row $r$ with offset equal to the row index. We will allow circulant matrices which are not square so that they are simply missing some of their last rows. We do however always assume that the number of rows is no more than the number of columns. For example, consider the following $3\times5$ circulant matrix.

$$\begin{pmatrix}1&0&1&1&1\\ 1&1&0&1&1\\ 1&1&1&0&1\end{pmatrix}$$

We say a matrix has property $X$ if it contains two non-empty sets of columns with non-identical indices which have the same (vector) sum. The vector sum of two columns is simply an element-wise summation of the two columns. That is the sum of two columns containing $x$ elements each is another column containing $x$ elements.

The matrix above trivially has property $X$ as the first and last columns are the same. The identity matrix never has property $X$.

If we just remove the last column of the matrix above then we get an example which does not have property $X$. The score of a matrix is defined to be the number columns divided by the number of rows. The following matrix therefore does not have property $X$ and gives a score of $4/3$.

\begin{pmatrix}1&0&1&1\\ 1&1&0&1\\ 1&1&1&0\end{pmatrix}$$

The task they were given is to find the highest scoring circulant matrix whose entries are all 0 or 1 and which does not have property $X$.

So far the numerical evidence points towards an upper bound of two.

Is there an upper bound of $2$ for this score?


The highest scoring matrix found so far has a score of 36/19 by Peter Taylor. This has 000001001010110001000101001111111111 as the first row.

$\endgroup$
  • $\begingroup$ Related $\endgroup$ – Peter Taylor Nov 15 '14 at 11:16
  • $\begingroup$ For identity matrix all columns have a vector sum of 1. Then why it does not have property X? $\endgroup$ – arindam mitra Nov 20 '14 at 16:50
  • $\begingroup$ @arindammitra The property is to do with vector sums. So no two subsets of columns in the identity matrix have the same vector sum. $\endgroup$ – user66307 Nov 20 '14 at 18:15
0
$\begingroup$

I think any nxm circulant matrices (where m=n+1) of this form will not have property X, with all entries 0 or 1

$$\begin{pmatrix}1&0&1&1&\cdots&1\\ 1&1&0&1&\cdots&1\\ 1&1&1&0&\cdots&1\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\ 1&1&1&1&\cdots&0\end{pmatrix}$$

So the score of a matrix of this form is $$S=\frac{n+1}{n}$$

S is largest when n=1, thus the max possible score is $$S_{max}=\frac{2}{1}=2$$

However a 1x2 matrix is just a row vector $$\begin{pmatrix}1&0\end{pmatrix}$$ and not a circulant matrix

Thus the highest scoring required matrix is a 2x3 matrix of the form $$\begin{pmatrix}1&0&1\\1&1&0\end{pmatrix}$$

with max score $$S=\frac{3}{2}=1.5$$

================

EDIT (Attempt to fix my answer using the advice pointed out by Lembik)

From the requirements of property X, it seems any circulant (0,1) matrix must not have any columns identical

In addition, any column cannot be the linear combination of any 2 other columns

It is pointed out by Lembik that the following matrix

$$\begin{pmatrix}1&0&1\\1&1&0\end{pmatrix}$$

has property X since

$$\begin{pmatrix}1\\1\end{pmatrix}=\begin{pmatrix}1\\0\end{pmatrix}+\begin{pmatrix}0\\1\end{pmatrix}$$

In order to construct a matrix B such that it does not have property X and has no empty columns, it must first have unique non empty columns like so (or permultation thereof):

$$\begin{pmatrix}1&0&1&1&\cdots&1\\ 1&1&0&1&\cdots&1\\ 1&1&1&0&\cdots&1\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\ 1&1&1&1&\cdots&0\end{pmatrix}$$

The score of a matrix of this form is $$S=\frac{m}{n}$$

S is largest when n=1

However a 1xm matrix is just a row vector e.g. for 1x2 matrix $$\begin{pmatrix}1&0\end{pmatrix}$$ and not a circulant matrix, and since 0+1=1 as pointed out by the PPCG link, it has property X

For n=2, the only way there could be unique columns that are not linear combination of any two other columns is when m=2, but this violates the constraint m>n

Thus nxm where m>n, n must be > 2

We also note that for the case where n=3, m has to be < 5 as otherwise the exist a column which will either be non unique or a linear combination of any 2 of the existing columns (since all entries are restricted to 0 or 1)

Thus for n=3, m must = 4

We knew that by finding the limit of S as $$n \rightarrow \infty$$ is zero.

Therefore the highest scoring matrix must have the smallest m and n

Therefore the set of highest scoring required circulant matrices are (there are 24)

$$B=\begin{pmatrix}1&0&1&1\\1&1&0&1\\1&1&1&0\end{pmatrix}, \begin{pmatrix}1&0&1&1\\1&1&1&0\\1&1&0&1\end{pmatrix},\begin{pmatrix}1&1&0&1\\1&0&1&1\\1&1&1&0\end{pmatrix},\begin{pmatrix}1&1&0&1\\1&1&1&0\\1&0&1&1\end{pmatrix},\begin{pmatrix}1&1&1&0\\1&0&1&1\\1&1&0&1\end{pmatrix},\begin{pmatrix}1&1&1&0\\1&1&0&1\\1&0&1&1\end{pmatrix}\\\begin{pmatrix}1&1&1&0\\1&1&0&1\\0&1&1&1\end{pmatrix} etc.$$

with max score $$S=\frac{4}{3}=1.3333...$$

$\endgroup$
  • 1
    $\begingroup$ This isn't correct. First, take your example 2x3 matrix. The first columns = the sum of columns 2 and 3. $\endgroup$ – user66307 Nov 14 '14 at 17:11
  • 1
    $\begingroup$ I am afraid this is still wrong. There are plenty of matrices with higher scores. For example, consider the 8 by 13 circulant matrix with 0001001101011 as the first row. $\endgroup$ – user66307 Nov 15 '14 at 7:55
  • 1
    $\begingroup$ It's not actually the case that "any column cannot be the linear combination of any 2 other columns" - if it were then the upper bound would be 1. The point is that general linear combination allows multiples other than 0 or 1, whereas property X does not. $\endgroup$ – Peter Taylor Nov 15 '14 at 11:12

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.