The origin of this question is that I found a way to 'eliminate' vertex weights from weighted $K_n$ graphs, i.e. if one assumes that the weight $w_{ij}$ of edge $e_{ij}$ can be expressed as $\pi_i+\omega_{ij}+\pi_j$ with vertex potentials $\pi_i$ and $pi_j$, then it is possible to recover the $\omega_{ij}$.
I then was curious about revovering the vertex potentials and to that end set up system of linear equations obtained from the edges on a Hamilton cycle.
After an appropriate relabeling of the vertices the equations are of the form $\pi_i+\pi_{i+1}\ =\ w_{i,i+1}-\omega_{i,i+1};\quad 0\le\ i\ \le n,\quad n+1:=0$

Initially much to my surprise, it turned out that for the determinant of the associated matrix, one has $$\begin{vmatrix} 1 & 1 & 0 & 0&0&\cdots &0 & 0\\ 0 & 1& 1& 0&0&\cdots& 0&0\\ 0 & 0&1&1&0&\cdots&0&0\\ \vdots &\vdots & \ddots & \ddots & \ddots&\ddots&\vdots&\vdots\\ 0 &0& \cdots &0&1&1&0&0\\ 0 & 0 & \cdots &0 & 0&1&1&0\\ 1 & 0 &\cdots&0&0&0&0&1 \end{vmatrix}\ =\ 0\iff n\equiv0\mod2$$ which means that the unknown vertex potentials can only be determined, if their number is odd.

After a bit of thinking about that observation it became clear that the determinant of analogous matrices that have $m$ consecutive $1$s instead of two shifted cyclically by 1 to the right from one row to the next, is apparently non-zero exactly if $m$ and $n$ are relatively prime.


is there a non-trivial explanation for the phenomen that the solvability of related problems, whose only discernible essential difference is the number $n$ of equations, depends on number theoretic properties of the relation between $n$ and a fixed set of parameters, that are independent of $n$?
The arguments I have in mind would only be based on the "original" statement of the problem and not on their "translation" to a system of linear equations.
Ideally the arguments would be understandable without a background in linear algebra.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.