Title: Theory / Unimportant / CS / Algo / Linear and integer programming / Schrijver{ / 2 Lattices and Linear Diophantique Equations
Tags: fromMath fromAlgorithm hasNotNewEffectReturnsMeaning hasSeenConjDef mathToDef mathToSee oldAlgoNewName EquivalentButNoIntermediate TypToQuestion addIntermediateCard

Name: A matrix in Hermite normal form
Definition: has full row rank
Page: 045
Chapter: 4
Section: 1
Definition2: is of the form \([B0]\) with \(B\)
Conjdef: A matrix wich
Definition3: non singular,
Extra: Representation
Definition4: lower triangular,
Definition5: nonnegative
Definition6: each row having a unique maximum entry which is located on the main diagonal of \(B\).

Name: The elementary (unimodular) column operation
Definition: Exchanging two columns
Page: 045
Chapter: 4
Section: 1
Definition2: Multiplying a column by -1
Conjdef: All of
Definition3: Adding an integral multiple of one column to another column.

Page: 045
Implementation: a series of elementary column operations
Section: 1
Chapter: 4, 4, 5, 5
Variables: \(m,n\in\mathbb N\),
\(A=\left(\begin{array}{lll}\alpha_{1,1}&\dots&\alpha_{1,n}\\\vdots&&\vdots\\\alpha_{m,1}&\dots&\alpha_{m,n}\end{array}\right)\subseteq\mathbb Q^{m\times n}\)
Name: Hermite normal form theorem
Time complexity: polynomial time
Returns: Hermite normal form whose rows generates the same group
Index: 1,2, 2,3
Kind: Theo, Cor
Typ: Unique result
Assuming: rational matrix of full row rank
Space complexity: polynomially bounded in the size of the input.

Smaller0: \(Ax=b\) has an integral solution \(x\)
Greater0: for all \(y\), having \(yA\) integral implies that \(yb\) is an integer
Page: 046
Chapter: 4
Section: 1
Variables: \(m,n\in\mathbb N\)
\(A\subseteq\mathbb Q^{m\times n}\)
\(b\in\mathbb Q^m\)
Index: 1a
Kind: Cor
Smaller to greater: iff
Hide middle: yes

Name: The groups generated by \(a_1,\dots,a_m\)
Page: 047
Chapter: 4
Section: 1
Variables: \(a_1,\dots,a_m\in\mathbb Q^n\)
Index: 1b
Kind: cor
Typ: A lattice

Smaller0: the gcd of the subdeterminants of \(A\) of order \(m\) is 1
Greater0: the system \(Ax=b\) has an integral solution \(x\), for each integral vector \(b\)
Page: 047
Chapter: 4
Section: 1
Variables: \(A\) be an integral \(m\times n\)-matrix of full row rank.
Index: 1c
Kind: Cor
Smaller to greater: iff
Intermediate: for each vector \(y\), if \(yA\) is integral, then \(y\) is integral

Name: Unimodular matrix
Definition: The result of elementary column operations applied to the identity matrix.
Page: 048
Chapter: 4
Section: 3
Variables: \(m\in\mathbb N\),
Kind: Theo
Definition2: A nonsingular, integral matrix whose determinant \(\pm1\)
Definition3: the inverse of an unimodular matrix
Definition4: the lattice generated by the columns of \(U\) is \(\mathbb Z^n\)
Definition5: A matrix whose Hermite normal form is the identity matrix

Smaller0: the columns of \(A_1\) and those of \(A_2\) generate the same lattice
Greater0: \(A_1\) comes from \(A_2\) by elementary column operations
Page: 48, 049
Chapter: 4
Section: 2, 3
Variables: \(A_1\) and \(A_2\) be integral matrices of full row rank
\([B_i 0]\) the Hermite normal form of \(A_i\)
Index: 3a
Kind: Theo, Cor
Smaller to greater: iff
Smallest: \(B_1=B_2\)
Greatest: \(A_2=A_1U\) for some unimodular matrix \(U\)

Smaller0: the columns of \(A\) and those of \(A'\) generate the same lattice
Greater0: \(A'=AU\) for some unimodular matrix \(U\)
Page: 049
Chapter: 4
Section: 3
Variables: \(m\in\mathbb N\)
\(A,A'\subseteq\mathbb Q^{m\times m}\).
Index: a
Kind: Cor
Smaller to greater: iff
Smallest: \(A'\) comes from \(A\) by elementary column operations

Page: 052
Implementation: Let \[A_1=\left(\begin{array}{ll}a&b\\1&0\\0&1\\\end{array}\right)=\left(\begin{array}{ll}\alpha_ 1^0&\beta_1^0\\\beta_1^1&\alpha_1^1\\\gamma_1^0&\gamma_1^1\\\end{array}\right),\]
Loop:
w.l.o.g, up to exchanging columns, assume \(\alpha^0_k<\alpha^1_k\). If \(0=\alpha^0_k\), halt loop
Let \(A_{k+1}\) being \(A_k\) with the column of the smallest \(\alpha_k^i\) substracted \(\left\lfloor\frac{\alpha_k^{1-i} }{\alpha_k^{i} }\right\rfloor\) times from the other column. (w.l.o.g, assume \(\alpha^0_k<\alpha^1_k\))
\[A_k=\left(\begin{array}{ll}\alpha^0_k&\beta^1_k-\alpha_k^1\\\beta_k^0&\alpha_k^1-\frac{\beta_k^0\alpha_k^1}{\alpha_k^0}\\\gamma_k^0&\gamma_k^1-\frac{\gamma_k^0\alpha_k^1}{\alpha_k^0}\\\end{array}\right),\]
Return \(\gamma_k^0,\gamma_k^1\), for \(k\) maximal
Section: 1
Chapter: 5
Variables: \(a^0,a^1\) integers
Name: The Euclidean algorithm
Returns: Two integers such that \(\gamma^0a^0+\gamma^1a^1=\gcd(a^0,a^1)\)

Question: It satisfies the equalities
Answer: \[\beta^i_k a^i+\gamma_k^i a^{1-i}=\alpha_k^i\]
Page: 052
Chapter: 5
Section: 1
Variables: \(a^0,a^1\) integers,
\[A_k=\left(\begin{array}{ll}\alpha^0_k&\beta^1_k\\\beta_k^0&\alpha_k^1\\\gamma_k^0&\gamma_k^1\\\end{array}\right)\]
with
\[A_1=\left(\begin{array}{ll}a&b\\1&0\\0&1\\\end{array}\right),\]
and \(A_{k+1}\) being \(A_k\) with the column of the smallest \(\alpha_k^i\) substracted \(\left\lfloor\frac{\alpha_k^{1-i} }{\alpha_k^{i} }\right\rfloor\) times from the other column.

Question: \(\beta_N^ia^i+\gamma_N^i a^{1-i}\) equals
Answer: \text{gcd}\((a^0,a^1)\)
Page: 052
Chapter: 5
Section: 1
Variables: \(a^0,a^1\) integers,
\[A_k=\left(\begin{array}{ll}\alpha^0_k&\beta^1_k\\\beta_k^0&\alpha_k^1\\\gamma_k^0&\gamma_k^1\\\end{array}\right)\]
with
\[A_1=\left(\begin{array}{ll}a&b\\1&0\\0&1\\\end{array}\right),\]
and \(A_{k+1}\) being \(A_k\) with the column of the smallest \(\alpha_k^i\) substracted \(\left\lfloor\frac{\alpha_k^{1-i} }{\alpha_k^{i} }\right\rfloor\) times from the other column.
\(N\) such that \(\alpha_N^i=0\)

Question: \(\beta_N^ia^{1-i}+\gamma_N^i a^{i}\) equals
Answer: 0
Page: 052
Chapter: 5
Section: 1
Variables: \(a^0,a^1\) integers,
\[A_k=\left(\begin{array}{ll}\alpha^0_k&\beta^1_k\\\beta_k^0&\alpha_k^1\\\gamma_k^0&\gamma_k^1\\\end{array}\right)\]
with
\[A_1=\left(\begin{array}{ll}a&b\\1&0\\0&1\\\end{array}\right),\]
and \(A_{k+1}\) being \(A_k\) with the column of the smallest \(\alpha_k^i\) substracted \(\left\lfloor\frac{\alpha_k^{1-i} }{\alpha_k^{i} }\right\rfloor\) times from the other column.

Question: Ptime algo to solve \(\sum_{i=1}^n a_i\xi_i=b\) with rational coefficient:
Answer: Case \(n=1\) trivial.
Case \(n>1\): Let \(a'=gcd(a_1,a_2)=a_1c+a_2e\). By induction, find a solution \(x\) to \(a'x'+\sum_{i=3}^n a_i\xi_i=b\). Then take \(x_1=cx'\) and \(x_2=ex'\).
Page: 054
Chapter: 5
Section: 1
Index: 1a
Kind: Cor

Name: Dirichlet's theorem
Definition: There exists \(p,q\in\mathbb N\) such that \(\left |a-\frac pq\right|<\frac\epsilon q\text{ and }1\le q\le \frac 1\epsilon\).
Page: 060
Chapter: 6
Section: 1
Variables: \(a\in\mathbb R\)
\(0<\epsilon\le 1\).
Kind: Theo

Name: The fraction part of \(r\)
Definition: \(r-\lfloor r\rfloor\).
Page: 60
Chapter: 6
Section: 1
Variables: \(r\in\mathbb R\)
Notation: \(\{r\}\)

Smaller0: \(r\)
Greater0: \(\lfloor\gamma_1 \rfloor+\frac{1}{\lfloor \gamma_2\rfloor+\frac{1}{\dots+\frac{1}{\lfloor\gamma_{i-1}\rfloor+\frac{1}{\gamma_i} } } }\) for \(i\in\mathbb N\)
Page: 61
Chapter: 6
Section: 1
Variables: \(r\ge 0\)
Index: (4), (5)
Smaller to greater: is equal to
Hide middle: yes
Name: continued fraction method

Definition: \(r\) if \(n=1\)
Page: 61
Chapter: 6
Section: 1
Variables: \(r\ge 0\) real
\(n\in\mathbb N\)
Notation: \(\gamma_i\)
Index: (4), (5)
Definition2: \(\frac{1} {\{\gamma_i\} }\) for \(i>1\)
Conjdef: Either

Name: Convergents for \(r\)
Definition: \(\lfloor\gamma_1 \rfloor+\frac{1}{\lfloor \gamma_2\rfloor+\frac{1}{\dots+\frac{1}{\lfloor\gamma_{i-1}\rfloor+\frac{1}{\lfloor \gamma_i\rfloor } } } }\) for \(i\in\mathbb N\).
Page: 61
Chapter: 6
Section: 1
Variables: \(r\ge 0\)
Index: (6)
Denoted by: \(\left(\frac{p_i}{q_i}\right)_{i\in\mathbb N}\)

Smaller0: \(\left(\frac{p_i}{q_i}\right)_{i\ge 2}\)
Greater0: the convergents of \(\frac 1r\)
Page: 62
Chapter: 6
Section: 1
Variables: \(0<r\)
\(\left(\frac{p_i}{q_i}\right)_{i\ge 1}\) its convergent
Kind: Claim
Smaller to greater: is equal to
Hide middle: yes
Assuming: \(r<1\)

Page: 65
Implementation: the continued fraction method
Section: 1
Chapter: 6
Effect: Integers \(p\) and \(q\) as described in Dirichlet's theorem
Variables: \(0\le r\)
\(\epsilon>0\)
Time complexity: polynomial in \(r\)
Index: 2a
Kind: Cor
Assuming: \(r,\epsilon\) are rationals

Smaller0: \(|\alpha-p/q|<\frac1{2q^2}\)
Greater0: \(p/q\)
Page: 65
Chapter: 6
Section: 1
Variables: \(0\le\alpha\) real
\(p,q\in\mathbb N\)
Index: 3
Kind: Theo
Hide middle: yes
Greater1: occurs as convergent for \(\alpha\)

Q: The numbers of rationals \(p/q\) with \(1\le q\le M\) and \(|r-p/q|<\frac {M^{2} }2\) is [...]. Complexity of computing \(p/q\) is [property]
A: at most one; P time
Page: 66
Chapter: 6
Section: 1
Variables: \(0\le r\) and \(M>0\)
Index: 3a
Kind: Cor

Page: 68
Implementation: Assume \(D\) integral (multiplying by appropriate constant)
\(b^1_1,\dots,b^1_m\) the unit basis
todo
Section: 2
Chapter: 6
Effect: \(b_1,\dots,b_n\) such that [$]\norm{ b_1}\dots\norm{ b_n}\le 2^{n(n-1)/4}\sqrt{\text{det }D}[/$], with [$]\norm{ x} :=\sqrt{x^TDx}[/$]
Variables: \(D\in\mathbb Q^{n\times n}\) positive definite.
Time complexity: P
Index: 4
Kind: Theo
Typ: a basis of \(\mathbb Z^n\)

Q: There exists \(b_1,\dots,b_n\) [...] such that [...].
A: a basis of \(\Lambda\); \(\parallel b_1\parallel \dots\parallel b_n\parallel \le 2^{n(n-1)/4}\sqrt{|\text{det }D|}\), with \(\parallel x\parallel :=\sqrt{x^Tx}\)
Page: 71
Chapter: 6
Section: 2
Variables: \(D\in\mathbb Z^{n\times n}\) nonsingular generating a lattice \(\Lambda\)
Index: 4a
Kind: Cor

Smaller0: \(\Lambda\)
Greater0: nonzero whose norm is less than \[2\left(\frac{\text{det} \Lambda}{\text{Volume of the $n$-dimensional unit ball} }\right)^{1/n}\]
Page: 71
Chapter: 6
Section: 4
Variables: \(n\in\mathbb N\) and
\(\Lambda\) a \(n\)-dimensional lattice.
Index: (70)
Smaller to greater: contains
Hide middle: yes
Prefix Greater: a vector \(b\)
Greater1: assumed to be NP-complete
Greater to smaller: belongs to
Connect Greater0: Complexity of finding \(b\) is

Question: We can compute in P-time a vector \(b\in\Lambda\setminus\{0\}\) such that
Answer: its norm is at most \[2^{n(n-1)/4}(\text{det}A)^{1/n}\].
Page: 72
Chapter: 6
Section: 4
Variables: \(n\in\mathbb N\),
\(A\) a non-singular \(n\)-dimensional lattice,
\(\Lambda\) the lattice generated by the columns of \(A\)
Index: 4b
Kind: Cor

Question: There exists
Answer: \(1\le q\le 2^{n(n+1)/4}\epsilon^{-n}\) integer and \(p\in\mathbb Z^n\) such that [$]\norm{a-\frac 1qp}<\frac\epsilon q[/$].
Page: 73
Chapter: 6
Section: 3
Variables: \(n\in\mathbb N\),
\(0<\epsilon<1\) and
\(a\in\mathbb Q^n\)
Index: 4c
Kind: Cor
Name: Simultaneous diophantine approximation

Name: Unimodular matrix
Definition: The result of elementary column operations applied to the identity matrix.
Page: 048
Chapter: 4
Section: 3
Variables: \(m\in\mathbb N\),
\(U\subseteq\mathbb Q^{m\times m}\).
Kind: Theo
Definition2: A nonsingular, integral matrix whose determinant \(\pm1\)
Definition3: A matrix whose Hermite normal form is the identity matrix
Definition4: the lattice generated by the columns of \(U\) is \(\mathbb Z^n\)

Name: Unimodular matrices
Page: 49
Section: 3
Chapter: 4
Index: (v)
Kind: Theo
Under: inverse of matrix
Under2: product ?

Name: \(x\) is orthogonal relatively to \(y\)
Definition: \(x^\top Dy=0\)
Page: 68
Chapter: 6
Section: 2
Variables: \(D\in\mathbb Q^{n\times n}\),
\(x,y\in\mathbb Q^n\)
Notation: \(x\bot y\)
Index: 4
Kind: Theo