MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider given pairs of variables: $a_{ir1},a_{ir2}\in \mathbb{R}^{m \times m}$ and $a_{jr1},a_{jr2}\in \mathbb{R}^{m \times m}$, where $r \in \{1,2,\cdots,t\}$, consider the constraints:



with $i \ne j$ and $i,j \in \{1,2,\cdots,n\}$.

Let the smallest size of matrices such constraints as a function of $n$ and $t$ be $f(n,t)$. My primary question is how fast does $f(n,t)$ grow with $n$ and $t$? For a fixed $t$, let the growth be $f(n)[t]$. How fast does $f(n)[t]$ grow with $n$? Does $f(n,t) = O(\log^{c}{n})$ when $t=O(n^{q})$ for some $c \in \mathbb{N}$ and $\frac{1}{3} > q \in \mathbb{Q}$?

Secondly, how do you find such matrix solutions explicitly?

[Note: Each $a_{ijk}$ is a square matrix.]

What I know: For $t=1$, I am fairly certain $f(n,1) = n$. For any fixed $t$, I don't think we can do better (although not sure). What happens when $t$ is allowed to grow although with $n$ although at a sub-cubic rate w.r.t $n$ is something I am interested?

share|cite|improve this question
I am having parsing difficulties with this. Please rewrite it to be human-readable. – Igor Rivin Oct 11 '11 at 18:34
Is this clear? My older version was when $t=1$. – Turbo Oct 11 '11 at 19:09
Is $a_{ij1}$ a matrix for EACH i, or do you mean $(a_{ij})_{ij}$ is a matrix with entries $a_{ij}$ or...? I am confused... Maybe use two different letters instead of a third index to represent the pairs? – Per Alexandersson Oct 11 '11 at 19:53
each aijk is a matrix – Turbo Oct 11 '11 at 20:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.