Large submatrices of circulant matrices

Question

What properties of circulant matrices are inherited by their principal submatrices? To be more specific:

Given a square (zero-one) matrix $M$ of order $n$ with all elements on its main diagonal equal to each other, how to determine whether there is a circulant matrix of order at most $n^{1.01}$ of which $M$ is a principal submatrix?

I am not interested in the algorithmic aspect, but rather in the general properties that large principal submatrices of circulant matrices must have.

---

Added December 08,2017

A more comprehensible version of essentially the same question:

Given a square, zero-one matrix $M=(m_{ij})_{1\le i,j\le n}$ and an abelian group $G$ of order $n\le |G|<n^{1.01}$, we want to find a subset $A=\{a_1,\dotsc,a_n\}\subset G$ such that whenever $a_i-a_j=a_k-a_l$ holds for some $i,j,k,l\in[1,n]$, we have $m_{ij}=m_{kl}$. A trivial necessary condition is that all diagonal elements of $M$ are equal to each other. What are other necessary conditions?

Answer 1

More musing than answer. (Technically, it is wrong, because I am adding the coordinates wrong. I think I should be summing n_i -n_j instead of n_i. I will edit in a correction later.) (Later: I should be thinking difference sets, not sum sets. I imagine this correspondence between difference sets and the above posted question is in the literature. I hope to do a proper edit by tomorrow.)

I imagine that principal means "having the diagonal come from the diagonal of the large matrix". Then a square submatrix is determined by (the entries of the large submatrix, of course, and) a set of n integers, which are the coordinates of the columns and of the rows. Suppose we start the coordinates at zero and the rest are positive integers n_i in ascending order. Then the values of the ith jth entry of the sub matrix (for i less than j) are on the kth diagonal of the large matrix, where k is n_i + n_j. So this question is really a sumset question, as the large matrix is circulant, the entries depend only on the sum (of the coordinates from the n-set) of values.

Edit 2017.12.04: since the paragraph above was inspiring if wrong, I decided to add after it.

One thing to note about a square submatrix of large size of a circulant matrix, you can "project" the parts of the columns on one side or the other of the diagonal of the submatrix onto the last column (or row, depending on the diagonal of sub being above or below the diagonal) of the large matrix, which means that these column parts will share some differences unless the large matrix is really large and the projections are all disjoint as subsets of the last column. Thus embedding an arbitrary matrix of order n may need a matrix of order n choose 2.

Here is a criterion which is not computationally nice, but may help with a characterization. Let us embed a given matrix M in a larger circulant matrix so that M is a principal submatrix. Let the embedding be such that the first diagonal entry is at 1,1, and the difference between consecutive diagonal entries is measured by $a_i$, so we have the (i-1)th diagonal entry is at $(k,k)$ then the ith one is at $(k+a_i,k+a_i)$. Now let us look at the outer diagonals of M. The outermost diagonal (entry (1,n)) has only one entry, so lets look at the next one ((1,n-1) and (2,n)). If those entries are the same, we can't conclude much, but if they are different, then they embed in different diagonals and we have $a_1$ and $a_{n-1}$ must be distinct numbers. Similarly, going down the jth outer diagonals, when neighboring entries differ, we get. that $a_i$ is different from $a_{i+n-j}$. Now by themselves, these inequalities do not say much. However, if one gets a group of $d=n^\epsilon$ numbers $a_i$ with no two equal, then the sum of these a's is about $d^2 /2$ or larger which would mean that there can't be an embedding if the larger matrix has order less than $n + d^2/2$. In particular, for such an embedding into order $n^{1.01}$, most of the $a_i$ have to be the same and small, so the diagonals of M can't wiggle much.

End edit 2017.12.04.

Gerhard "A Musing Is Sometimes Amusing" Paseman, 2017.12.02.