1
$\begingroup$

There are already detailed results on the solutions of linear equations over fields, but I'd like to inquire about any good conclusions regarding the solutions of linear equations over the integer ring $\mathbb{Z}$. Specifically, the issue arises from the first equation in the image. \begin{equation} \left(\begin{array}{cccc} a_{11} & a_{21} & \cdots & a_{m 1} \\ a_{12} & a_{22} & \cdots & a_{m 2} \\ \vdots & \vdots & \ddots & \vdots \\ a_{1 n} & a_{2 n} & \cdots & a_{m n} \end{array}\right)\left(\begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_m \end{array}\right)=\left(\begin{array}{c} 0(modz_1) \\ 0(modz_2) \\ \vdots \\ 0(modz_n) \end{array}\right) \end{equation} Considering all numbers are in $\mathbb{Z}$, I know that the first equation given in the image must have a non-zero solution in $\mathbb{Z}$, such as taking the product of $z_1z_2\cdots z_n$. Essentially, this corresponds to whether the second equation has a solution, where $k_i$ can be any integer. \begin{equation} \left(\begin{array}{cccc} a_{11} & a_{21} & \cdots & a_{m 1} \\ a_{12} & a_{22} & \cdots & a_{m 2} \\ \vdots & \vdots & \ddots & \vdots \\ a_{1 n} & a_{2 n} & \cdots & a_{m n} \end{array}\right)\left(\begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_m \end{array}\right)=\left(\begin{array}{c} k_1z_1 \\ k_2z_2 \\ \vdots \\ k_nz_n \end{array}\right) \end{equation} However, on this basis, I also want to know if there are solutions with an odd sum (or, in other words, solutions with a 1-norm as odd). So, there is the third equation, where the coefficient matrix is augmented with a row of 1's, and the non-homogeneous term corresponds to an odd number. This corresponds to whether the first equation has a solution with an odd sum. I wonder if there are any friends who are familiar with this and could provide some guidance. \begin{equation} \left(\begin{array}{cccc} 1 & 1 & \cdots & 1 \\ a_{11} & a_{21} & \cdots & a_{m 1} \\ a_{12} & a_{22} & \cdots & a_{m 2} \\ \vdots & \vdots & \ddots & \vdots \\ a_{1 n} & a_{2 n} & \cdots & a_{m n} \end{array}\right)\left(\begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_m \end{array}\right)=\left(\begin{array}{c} 2 t_0+1 \\ k_1 z_1 \\ k_2 z_2 \\ \vdots \\ k_n z_n \end{array}\right) \end{equation}

$\endgroup$
11
  • 1
    $\begingroup$ The problem arises from my curiosity about what conditions a Cayley graph must satisfy to be a bipartite graph. $\endgroup$ Commented May 1 at 7:43
  • 5
    $\begingroup$ If the equations are in different rings, $\mathbb{Z}/z_i\mathbb{Z}$ here, I wouldn't put them in a matrix equation like you do in the first displayed equation. The last equation can be written as $M\, \mathbf{v} = \mathbf{b}$ with unknown $\mathbf{v}=(x_1,\dots,x_m,k_1,\dots,k_n)$ and now you simply have linear algebra over $\mathbb{Z}$. See chapter 2 in Cohen's "A course in computational algebraic number theory" $\endgroup$ Commented May 1 at 8:04
  • $\begingroup$ I hope you know when a circulant graph (a Cayley graph) over the finite cyclic group is bipartite. Similar generalizations can be had for Cayley graphs over dihedral groups and, with some more specifications, for Cayley graphs over nilpotent groups, as well as symmetric groups. $\endgroup$
    – vidyarthi
    Commented May 1 at 10:55
  • 2
    $\begingroup$ See "On systems of linear diophantine equations" by Lazebnik (published in Mathematics Magazine). Linear systems over the integers can be solved using the Smith normal form of the coefficient matrix. $\endgroup$
    – Josh
    Commented May 1 at 14:09
  • 2
    $\begingroup$ Linear equations over integers are traditionally addressed in terms of lattices. E.g. see this introductory text: sites.math.washington.edu/~rothvoss/lecturenotes/… $\endgroup$ Commented May 2 at 4:44

0

You must log in to answer this question.