Skip to main content
added 37 characters in body
Source Link
David E Speyer
  • 156.2k
  • 14
  • 419
  • 763

$\def\ZZ{\mathbb{Z}}$No answers after a week so, for the record, I'll write up my proof. Let $v_1^0$, $v_1^1$, $v_2^0$, $v_2^1$, ..., $v_n^0$, $v_n^1$ be as in the original post.

Rename $v_i^0$ to $e_i$ and $v_j^1$ to $f_j$. By hypothesis, $(e_1, e_2, \ldots, e_n)$ is a basis of $\ZZ^n$ and without loss of generality, we can assume it is the standard one. Let $f_j = \sum_i a_{ij} e_i$.

Lemma 1 We have $a_{ii} = -1$.

Proof Use the assumption that $\det(e_1, e_2, \ldots, e_{i-1}, f_i, e_{i+1}, \ldots, e_n) = -1$. $\square$

Now, define a directed graph $\Gamma$. The vertex set is $\{ 1,2,\ldots, n \}$, and there is an edge $i \to j$ if $i \neq j$ and $a_{ij}$ is nonzero. There are no edges of the form $i \to i$.

Lemma 2 The directed graph $\Gamma$ is acyclic.

Proof Suppose, to the contrary that $\Gamma$ has a directed cycle. Let $j_1 \to j_2 \to \cdots \to j_k \to j_1$ be the shortest directed cycle. (Note that we could have $k=2$, but we can't have $k=1$, since $\Gamma$ has no loops.) Then there are no other edges between any $j_a$ and $j_b$ other than those in the cycle. Let $J = \{ j_1, j_2, \ldots, j_k \}$.

Now, consider $\det{\big(} \{ e_i : i \not\in J \} \cup \{ f_j : j \in J \} {\big)}$. On the diagonal, we get $(-1)^k$ (using Lemma 1). The only other permutation which can contribute to the determinant is the cycle $(j_1 j_2 \cdots j_k)$, and it contributes $\prod_{r=1}^k a_{j_r j_{r+1}}$. (The inner subscript is periodic modulo $k$.) So the determinant is $(-1)^k + (-1)^{k-1} \prod_{r=1}^k a_{j_r j_{r+1}}$.

Since $j_r \to j_{r+1}$ is an edge of $\Gamma$, we have $a_{j_r j_{r+1}} \neq 0$, so $\prod_{r=1}^k a_{j_r j_{r+1}} \neq 0$ and the determinant is not $(-1)^k$. But our hypothesis exactly is that the determinant should be $(-1)^k$, a contradiction. $\square$

So, we can reorder our subscripts so that $\Gamma$ only has edges $i \to j$ for $i>j$$i<j$. Then the $$v_j^0+v_j^1 = e_j + \left( - e_j + \sum_{i<j} a_{ij} e_i \right) = \sum_{i<j} a_{ij} v_i^0$$ as desired conclusion $(2)'$ follows for this ordering of the subscripts.    QED

$\def\ZZ{\mathbb{Z}}$No answers after a week so, for the record, I'll write up my proof. Let $v_1^0$, $v_1^1$, $v_2^0$, $v_2^1$, ..., $v_n^0$, $v_n^1$ be as in the original post.

Rename $v_i^0$ to $e_i$ and $v_j^1$ to $f_j$. By hypothesis, $(e_1, e_2, \ldots, e_n)$ is a basis of $\ZZ^n$ and without loss of generality, we can assume it is the standard one. Let $f_j = \sum_i a_{ij} e_i$.

Lemma 1 We have $a_{ii} = -1$.

Proof Use the assumption that $\det(e_1, e_2, \ldots, e_{i-1}, f_i, e_{i+1}, \ldots, e_n) = -1$. $\square$

Now, define a directed graph $\Gamma$. The vertex set is $\{ 1,2,\ldots, n \}$, and there is an edge $i \to j$ if $i \neq j$ and $a_{ij}$ is nonzero. There are no edges of the form $i \to i$.

Lemma 2 The directed graph $\Gamma$ is acyclic.

Proof Suppose, to the contrary that $\Gamma$ has a directed cycle. Let $j_1 \to j_2 \to \cdots \to j_k \to j_1$ be the shortest directed cycle. (Note that we could have $k=2$, but we can't have $k=1$, since $\Gamma$ has no loops.) Then there are no other edges between any $j_a$ and $j_b$ other than those in the cycle. Let $J = \{ j_1, j_2, \ldots, j_k \}$.

Now, consider $\det{\big(} \{ e_i : i \not\in J \} \cup \{ f_j : j \in J \} {\big)}$. On the diagonal, we get $(-1)^k$ (using Lemma 1). The only other permutation which can contribute to the determinant is the cycle $(j_1 j_2 \cdots j_k)$, and it contributes $\prod_{r=1}^k a_{j_r j_{r+1}}$. (The inner subscript is periodic modulo $k$.) So the determinant is $(-1)^k + (-1)^{k-1} \prod_{r=1}^k a_{j_r j_{r+1}}$.

Since $j_r \to j_{r+1}$ is an edge of $\Gamma$, we have $a_{j_r j_{r+1}} \neq 0$, so $\prod_{r=1}^k a_{j_r j_{r+1}} \neq 0$ and the determinant is not $(-1)^k$. But our hypothesis exactly is that the determinant should be $(-1)^k$, a contradiction. $\square$

So, we can reorder our subscripts so that $\Gamma$ only has edges $i \to j$ for $i>j$. Then the desired conclusion $(2)'$ follows for this ordering of the subscripts.  QED

$\def\ZZ{\mathbb{Z}}$No answers after a week so, for the record, I'll write up my proof. Let $v_1^0$, $v_1^1$, $v_2^0$, $v_2^1$, ..., $v_n^0$, $v_n^1$ be as in the original post.

Rename $v_i^0$ to $e_i$ and $v_j^1$ to $f_j$. By hypothesis, $(e_1, e_2, \ldots, e_n)$ is a basis of $\ZZ^n$ and without loss of generality, we can assume it is the standard one. Let $f_j = \sum_i a_{ij} e_i$.

Lemma 1 We have $a_{ii} = -1$.

Proof Use the assumption that $\det(e_1, e_2, \ldots, e_{i-1}, f_i, e_{i+1}, \ldots, e_n) = -1$. $\square$

Now, define a directed graph $\Gamma$. The vertex set is $\{ 1,2,\ldots, n \}$, and there is an edge $i \to j$ if $i \neq j$ and $a_{ij}$ is nonzero. There are no edges of the form $i \to i$.

Lemma 2 The directed graph $\Gamma$ is acyclic.

Proof Suppose, to the contrary that $\Gamma$ has a directed cycle. Let $j_1 \to j_2 \to \cdots \to j_k \to j_1$ be the shortest directed cycle. (Note that we could have $k=2$, but we can't have $k=1$, since $\Gamma$ has no loops.) Then there are no other edges between any $j_a$ and $j_b$ other than those in the cycle. Let $J = \{ j_1, j_2, \ldots, j_k \}$.

Now, consider $\det{\big(} \{ e_i : i \not\in J \} \cup \{ f_j : j \in J \} {\big)}$. On the diagonal, we get $(-1)^k$ (using Lemma 1). The only other permutation which can contribute to the determinant is the cycle $(j_1 j_2 \cdots j_k)$, and it contributes $\prod_{r=1}^k a_{j_r j_{r+1}}$. (The inner subscript is periodic modulo $k$.) So the determinant is $(-1)^k + (-1)^{k-1} \prod_{r=1}^k a_{j_r j_{r+1}}$.

Since $j_r \to j_{r+1}$ is an edge of $\Gamma$, we have $a_{j_r j_{r+1}} \neq 0$, so $\prod_{r=1}^k a_{j_r j_{r+1}} \neq 0$ and the determinant is not $(-1)^k$. But our hypothesis exactly is that the determinant should be $(-1)^k$, a contradiction. $\square$

So, we can reorder our subscripts so that $\Gamma$ only has edges $i \to j$ for $i<j$. Then $$v_j^0+v_j^1 = e_j + \left( - e_j + \sum_{i<j} a_{ij} e_i \right) = \sum_{i<j} a_{ij} v_i^0$$ as desired.  QED

Source Link
David E Speyer
  • 156.2k
  • 14
  • 419
  • 763

$\def\ZZ{\mathbb{Z}}$No answers after a week so, for the record, I'll write up my proof. Let $v_1^0$, $v_1^1$, $v_2^0$, $v_2^1$, ..., $v_n^0$, $v_n^1$ be as in the original post.

Rename $v_i^0$ to $e_i$ and $v_j^1$ to $f_j$. By hypothesis, $(e_1, e_2, \ldots, e_n)$ is a basis of $\ZZ^n$ and without loss of generality, we can assume it is the standard one. Let $f_j = \sum_i a_{ij} e_i$.

Lemma 1 We have $a_{ii} = -1$.

Proof Use the assumption that $\det(e_1, e_2, \ldots, e_{i-1}, f_i, e_{i+1}, \ldots, e_n) = -1$. $\square$

Now, define a directed graph $\Gamma$. The vertex set is $\{ 1,2,\ldots, n \}$, and there is an edge $i \to j$ if $i \neq j$ and $a_{ij}$ is nonzero. There are no edges of the form $i \to i$.

Lemma 2 The directed graph $\Gamma$ is acyclic.

Proof Suppose, to the contrary that $\Gamma$ has a directed cycle. Let $j_1 \to j_2 \to \cdots \to j_k \to j_1$ be the shortest directed cycle. (Note that we could have $k=2$, but we can't have $k=1$, since $\Gamma$ has no loops.) Then there are no other edges between any $j_a$ and $j_b$ other than those in the cycle. Let $J = \{ j_1, j_2, \ldots, j_k \}$.

Now, consider $\det{\big(} \{ e_i : i \not\in J \} \cup \{ f_j : j \in J \} {\big)}$. On the diagonal, we get $(-1)^k$ (using Lemma 1). The only other permutation which can contribute to the determinant is the cycle $(j_1 j_2 \cdots j_k)$, and it contributes $\prod_{r=1}^k a_{j_r j_{r+1}}$. (The inner subscript is periodic modulo $k$.) So the determinant is $(-1)^k + (-1)^{k-1} \prod_{r=1}^k a_{j_r j_{r+1}}$.

Since $j_r \to j_{r+1}$ is an edge of $\Gamma$, we have $a_{j_r j_{r+1}} \neq 0$, so $\prod_{r=1}^k a_{j_r j_{r+1}} \neq 0$ and the determinant is not $(-1)^k$. But our hypothesis exactly is that the determinant should be $(-1)^k$, a contradiction. $\square$

So, we can reorder our subscripts so that $\Gamma$ only has edges $i \to j$ for $i>j$. Then the desired conclusion $(2)'$ follows for this ordering of the subscripts. QED

Post Made Community Wiki by David E Speyer