2
$\begingroup$

I have the following set of equation systems, and I would like to find a short, formal way to write it down. My main difficulty is that I cannot find a good way to write the indices of the variables $\omega$. Any suggestion is highly apprechiated.

n=4: $$\omega_{A,B,a,b}\cdot\omega_{C,D,c,d}+\omega_{A,C,a,c}\cdot\omega_{B,D,b,d}+\omega_{A,D,a,d}\cdot\omega_{B,C,b,c}=\delta_{a,b}\cdot\delta_{b,c}\cdot\delta_{c,d}$$ with $\omega_{X,Y,x,y} \in \mathbb{C}$, and $x,y \in \{0,1\}$. This leads to 24 independent variables ($\omega_{A,B,0,0}$, $\omega_{A,B,0,1}$, $\omega_{A,B,1,0}$, $\omega_{A,B,1,1}$, $\omega_{A,C,0,0}$, $\omega_{A,C,0,1}$, $\omega_{A,C,1,0}$, $\omega_{A,C,1,1}$, $\omega_{A,D,0,0}$, $\omega_{A,D,0,1}$, $\omega_{A,D,1,0}$, $\omega_{A,D,1,1}$, $\omega_{B,C,0,0}$, $\omega_{B,C,0,1}$, $\omega_{B,C,1,0}$, $\omega_{B,C,1,1}$, $\omega_{B,D,0,0}$, $\omega_{B,D,0,1}$, $\omega_{B,D,1,0}$, $\omega_{B,D,1,1}$, $\omega_{C,D,0,0}$, $\omega_{C,D,0,1}$, $\omega_{C,D,1,0}$, $\omega_{C,D,1,1}$), and 16 equations:

$$ \omega_{A,B,0,0}\cdot\omega_{C,D,0,0}+\omega_{A,C,0,0}\cdot\omega_{B,D,0,0}+\omega_{A,D,0,0}\cdot\omega_{B,C,0,0}=1\\ \omega_{A,B,0,0}\cdot\omega_{C,D,0,1}+\omega_{A,C,0,0}\cdot\omega_{B,D,0,1}+\omega_{A,D,0,1}\cdot\omega_{B,C,0,0}=0\\ \omega_{A,B,0,0}\cdot\omega_{C,D,1,0}+\omega_{A,C,0,1}\cdot\omega_{B,D,0,0}+\omega_{A,D,0,0}\cdot\omega_{B,C,0,1}=0\\ \omega_{A,B,0,0}\cdot\omega_{C,D,1,1}+\omega_{A,C,0,1}\cdot\omega_{B,D,0,1}+\omega_{A,D,0,1}\cdot\omega_{B,C,0,1}=0\\ $$ $$ \omega_{A,B,0,1}\cdot\omega_{C,D,0,0}+\omega_{A,C,0,0}\cdot\omega_{B,D,1,0}+\omega_{A,D,0,0}\cdot\omega_{B,C,1,0}=0\\ \omega_{A,B,0,1}\cdot\omega_{C,D,0,1}+\omega_{A,C,0,0}\cdot\omega_{B,D,1,1}+\omega_{A,D,0,1}\cdot\omega_{B,C,1,0}=0\\ \omega_{A,B,0,1}\cdot\omega_{C,D,1,0}+\omega_{A,C,0,1}\cdot\omega_{B,D,1,0}+\omega_{A,D,0,0}\cdot\omega_{B,C,1,1}=0\\ \omega_{A,B,0,1}\cdot\omega_{C,D,1,1}+\omega_{A,C,0,1}\cdot\omega_{B,D,1,1}+\omega_{A,D,0,1}\cdot\omega_{B,C,1,1}=0\\ $$ $$ \omega_{A,B,1,0}\cdot\omega_{C,D,0,0}+\omega_{A,C,1,0}\cdot\omega_{B,D,0,0}+\omega_{A,D,1,0}\cdot\omega_{B,C,0,0}=0\\ \omega_{A,B,1,0}\cdot\omega_{C,D,0,1}+\omega_{A,C,1,0}\cdot\omega_{B,D,0,1}+\omega_{A,D,1,1}\cdot\omega_{B,C,0,0}=0\\ \omega_{A,B,1,0}\cdot\omega_{C,D,1,0}+\omega_{A,C,1,1}\cdot\omega_{B,D,0,0}+\omega_{A,D,1,0}\cdot\omega_{B,C,0,1}=0\\ \omega_{A,B,1,0}\cdot\omega_{C,D,1,1}+\omega_{A,C,1,1}\cdot\omega_{B,D,0,1}+\omega_{A,D,1,1}\cdot\omega_{B,C,0,1}=0\\ $$ $$ \omega_{A,B,1,1}\cdot\omega_{C,D,0,0}+\omega_{A,C,1,0}\cdot\omega_{B,D,1,0}+\omega_{A,D,1,0}\cdot\omega_{B,C,1,0}=0\\ \omega_{A,B,1,1}\cdot\omega_{C,D,0,1}+\omega_{A,C,1,0}\cdot\omega_{B,D,1,1}+\omega_{A,D,1,1}\cdot\omega_{B,C,1,0}=0\\ \omega_{A,B,1,1}\cdot\omega_{C,D,1,0}+\omega_{A,C,1,1}\cdot\omega_{B,D,1,0}+\omega_{A,D,1,0}\cdot\omega_{B,C,1,1}=0\\ \omega_{A,B,1,1}\cdot\omega_{C,D,1,1}+\omega_{A,C,1,1}\cdot\omega_{B,D,1,1}+\omega_{A,D,1,1}\cdot\omega_{B,C,1,1}=1 $$

n=6: $$\omega_{A,B,a,b}\cdot\omega_{C,D,c,d}\cdot\omega_{E,F,e,f}+\omega_{A,B,a,b}\cdot\omega_{C,E,c,e}\cdot\omega_{D,F,d,f}+\omega_{A,B,a,b}\cdot\omega_{C,F,c,f}\cdot\omega_{D,E,d,e}\\ +\omega_{A,C,a,c}\cdot\omega_{B,D,b,d}\cdot\omega_{E,F,e,f}+\omega_{A,C,a,c}\cdot\omega_{B,E,b,e}\cdot\omega_{D,F,d,f}+\omega_{A,C,a,c}\cdot\omega_{B,F,b,f}\cdot\omega_{D,E,d,e}\\ +\omega_{A,D,a,d}\cdot\omega_{B,C,b,c}\cdot\omega_{E,F,e,f}+\omega_{A,D,a,d}\cdot\omega_{B,E,b,e}\cdot\omega_{C,F,c,f}+\omega_{A,D,a,d}\cdot\omega_{B,F,b,f}\cdot\omega_{C,E,c,e}\\ +\omega_{A,E,a,e}\cdot\omega_{B,C,b,c}\cdot\omega_{D,F,d,f}+\omega_{A,E,a,e}\cdot\omega_{B,D,b,d}\cdot\omega_{C,F,c,f}+\omega_{A,E,a,e}\cdot\omega_{B,F,b,f}\cdot\omega_{C,D,c,d}\\ +\omega_{A,F,a,f}\cdot\omega_{B,C,b,c}\cdot\omega_{D,E,d,e}+\omega_{A,F,a,f}\cdot\omega_{B,D,b,d}\cdot\omega_{C,E,c,e}+\omega_{A,F,a,f}\cdot\omega_{B,E,b,e}\cdot\omega_{C,D,c,d}=\delta_{a,b}\cdot\delta_{b,c}\cdot\delta_{c,d}\cdot\delta_{d,e}\cdot\delta_{e,f} $$

  • The rule is, that I multiply $m=\left(\frac{n}{2}\right)$ variables $\omega_{X_i,Y_i,x_i,y_i}$ ($\omega_{X_1,Y_1,x_1,y_1}\cdot\omega_{X_2,Y_2,x_2,y_2}\cdot\dots\cdot\omega_{X_m,Y_m,x_m,y_m}$), such that $X_0,Y_0,X_1,Y_1,\dots,X_m,Y_m$ contains each of the first $n$ letters in the alphabet exactly once.

  • There are $|\omega|=4\frac{n(n-1)}{2}$ variables and $|Q|=2^n$ equations.

  • The indices could be generalized to $x,y \in \{0,1,...,c-1\}$. Then $|\omega|=c^2\frac{n(n-1)}{2}$, $|Q|=c^n$.

Question. How can one write this infinite set of equation systems in a concise, formal way?

There are infinite equation systems because $n$ can be an arbitrary even integer, and $c$ can contain arbitrarily many terms.

PS: The current question is a reformulation of this question on graph theory, independent of graphs and perfect matchings.

.....

Improve this question
$\endgroup$
4
  • $\begingroup$ Why do you call it an "infinite" set of equation systems? Because you'll ultimately increase $c$ without bound? $\endgroup$
    – Michael Engelhardt
    Commented Sep 18, 2019 at 3:51
  • $\begingroup$ Because $n$ can be an arbitrary even number (and yes $c$ can become arbitrarily large), i specify that in the question now. thanks. $\endgroup$
    – Mario Krenn
    Commented Sep 18, 2019 at 4:26
  • $\begingroup$ Oh, so you don't mean a literal alphabet, where there is an upper bound on $n$? You mean an arbitrarily long alphabet of letters $X_i $, $i$ integer? $\endgroup$
    – Michael Engelhardt
    Commented Sep 18, 2019 at 4:34
  • $\begingroup$ yes thats right. but if you can solve it for $n$ up to 26, and arbitrary $c$, i guess your representation would already be quite good :-). $\endgroup$
    – Mario Krenn
    Commented Sep 18, 2019 at 4:44

2 Answers 2

Reset to default
3
+50
$\begingroup$

Let's use an alphabet $X_i $ indexed by an integer $1\leq i\leq n$, and also accompanying variables $x_i \in \{ 0,1,\ldots ,c-1 \} $. Up to now, it seems you've only defined the variables $\omega_{X_i, X_j, x_i, x_j} $ for $i<j$. For convenience, define also the auxiliary variables $\omega_{X_j, X_i, x_j, x_i} = \omega_{X_i, X_j, x_i, x_j} $ for $i<j$. Then, it seems to me your equations are $$ \frac{1}{(n/2)! 2^{n/2} } \sum_{m=1}^{n!} \prod_{j=1}^{n/2} \omega_{X_{P^{(m)}(2j-1)}, X_{P^{(m)}(2j)}, x_{P^{(m)}(2j-1)}, x_{P^{(m)}(2j)}} = \prod_{i=1}^{n-1} \delta_{x_i,x_{i+1} } $$ where $P^{(m)}(k)$ denotes the $k$-th entry in the $m$-th permutation of $1,2,\ldots ,n$. The prefactor $1/2^{n/2} $ arises because the sum over permutations generates also terms containing $\omega_{X_j, X_i, x_j, x_i} $ for $i<j$ in addition to your original $\omega_{X_i, X_j, x_i, x_j} $; the products contain $n/2$ factors $\omega $, and in each factor we can exchange $X_i \leftrightarrow X_j $, so we're overcounting each distinct term $2^{n/2} $ times. The prefactor $1/(n/2)!$ arises because we're generating all possible orderings of the factors $\omega $ in each product, so we're generating each distinct term $(n/2)!$ times. As you already indicate, there are $c^n $ equations because we can fix each of the variables $x_i $ to $c$ different choices.

Improve this answer
$\endgroup$
4
  • $\begingroup$ We can check the number of terms appearing on the left hand side, in terms of the alphabetic sequences you allow. For the first $\omega $, you always start with the first available letter, $A$, so that's fixed. But then you have $n-1$ choices for the second letter of the first $\omega $. In the second $\omega $, again the first letter is fixed, it's the one earliest in the alphabet among those remaining; then you have $n-3$ choices for the second letter. Thus, you generate $(n-1)!!$ terms. And indeed, dividing out the symmetry factor, I have $n!/(2^{n/2} (n/2)!) = (n-1)!!$ distinct terms. $\endgroup$
    – Michael Engelhardt
    Commented Sep 18, 2019 at 16:48
  • $\begingroup$ Wonderful thank you. I just tested explicitly the case $n$=4, and it works as expected, thank you. Now this is an extremly efficient formulation of the conjecture raised [here](mariokrenn.wordpress.com/graph-theory-question): This system of equations (for every $x_i$) has only solutions for $n$ even with $c$=2, or $n$<=4 with $c$=3. $\endgroup$
    – Mario Krenn
    Commented Sep 18, 2019 at 23:51
  • $\begingroup$ Thank you! Interesting that this is a way of formulating a graph theory question. I'm glad it helps. $\endgroup$
    – Michael Engelhardt
    Commented Sep 19, 2019 at 0:46
  • $\begingroup$ I have now used your formulation to actually state the full question here. Thank you again! $\endgroup$
    – Mario Krenn
    Commented Sep 19, 2019 at 4:07
1
$\begingroup$

The key will be to define some running variables that take on the appropriate values (which will be letters in your case) and then express which combinations are allowed. I'll give a simple example. Let $\alpha,\beta \in \{A,B,C,D\}$. I might then write down, for instance, $$w_{\alpha_1,\beta_1} + w_{\alpha_2,\beta_2} = \delta_{\alpha_1,\beta_1}$$ for all $\alpha_1 < \alpha_2,~\beta_1 < \beta_2$ where we take the natural ordering on $\{A,B,C,D\}$. This is perfectly mathematically acceptable and succinctly captures a large system of equations. You can do something analagous (if a bit more complex).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Hi Sheridan Grant, thanks for the answer. I think this does not really solve the question, because what i need is that the upper-case indices of the variables in each product contain the first $m$ letters in the alphabet. Please see my bullet point 1 after example $n=6$. $\endgroup$
    – Mario Krenn
    Commented Sep 15, 2019 at 22:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .