Title: Theory / Unimportant / CS / Algo / Linear and integer programming / Schrijver{ / 0 Introduction;
Tags: fromMath mathToDef hasSeenConjDef récupéré toBinaryFunction toBinaryRelation

Name: \(a\) divides \(b\)
Definition: \(\exists l\in\mathbb Z. al=b\).
Page: 003
Chapter: 1
Section: 2
Variables: \(a,b\in\mathbb R\).
Notation: \(a|b\)
Index: 4

Page: 003
Definition: \(y\) divides \(a-b\).
Chapter: 1
Section: 2
Variables: \(a,b\in\mathbb R\).
Notation: \(a\cong b\mod y\)

Name: The greatest common divisor of \(a\) and \(b\)
Definition: The greatest rational dividing \(a\) and \(b\).
Page: 003
Chapter: 1
Section: 2
Variables: \(a,b\in\mathbb Q\).
Index: 5
Abbreviation: \(gcd (a,b)\)

Name: A system of linear inequality
Definition: A set of \(m\) inequality of the form \(\sum_{i=1}^n a_{i,j}x_i<b_i\) with the same \(n\) variables.
Page: 005
Chapter: 1
Section: 3
Notation: \(Ax\le b\) with \(A\in\mathbb R^{m\times n}\), \(x\in\mathbb R^n\) and \(b\in\mathbb R^m\)
Index: 9

Name: A subsystem of \(Ax\le b\)
Definition: a subset of the inequalities.
Chapter: 1
Section: 3
Variables: \(Ax\le b\) be a system of linear inequality.

Name: An all-\(d\)-vector(matrix)
Definition: A vector(matrix) whose elements are all \(d\).
Page: 005
Chapter: 1
Section: 3
Variables: \(d\in\mathbb R\)

Definition: The transpose of \(x\).
Page: 005
Chapter: 1
Section: 3
Variables: \(m\in\mathbb N\),
\(x\in\mathbb Q^m\) a vector.
Notation: \(x^T\)

Name: The norm of \(x\)
Definition: \(\sqrt{x^Tx}\).
Page: 005
Chapter: 1
Section: 3
Variables: \(m\in\mathbb N\),
\(x\in\mathbb Q^m\) a vector.
Notation: \(\parallel x\parallel \)
Index: 10

Page: 005
Section: 3
Notation: \(d(x,y)\)
Variables: For \(x,y\in\mathbb Q^n\)
Chapter: 1
Name: The distance of \(x\) and \(y\)
Definition: \(\parallel x-y\parallel \).

Name: The ball with centre \(x\) and radius \(p\)
Definition: The set of \(y\in\mathbb Q^m\) such that \(d(x,y)\le p\).
Page: 005
Chapter: 1
Section: 3
Variables: \(x\in\mathbb Q^m\)
\(p\in\mathbb Q\)
Notation: \(B(x,p)\)
Index: 12

Smaller0: \(\parallel x\parallel _1\)
Greater0: \(\sum x_i\)
Page: 005
Chapter: 1
Section: 3
Variables: \(x\in\mathbb Q^m\)
Index: 13
Smaller to greater: =
Hide middle: yes

Smaller0: \(\parallel x\parallel _\infty\)
Greater0: \(max \{x_i\} \)
Page: 005
Chapter: 1
Section: 3
Variables: \(x\in\mathbb Q^m\).
Index: 13
Smaller to greater: =
Hide middle: yes

Name: A matrix which have full row(column) rank
Definition: A matrix in \(Q^{m\times n}\) whose row(column) rank is \(m\)(respectively \(n\)).
Page: 005
Chapter: 1
Section: 3
Variables: \(m,n\in\mathbb N\).

Name: A row(column) submatrix of \(A\)
Definition: The same matrix with rows (columns) deleted.
Page: 005
Chapter: 1
Section: 3
Variables: \(m,n\in\mathbb N\)
\(A\in\mathbb Q^{m\times n}\).

Name: Strictly upper triangle matrix
Definition: Upper triangle matrix with a 0-diagonal.
Page: 005
Chapter: 1
Section: 3
Variables: \(m\in\mathbb N\)
\(A\in\mathbb Q^{m\times m}\).

Definition: the square matrix with 0 apart from the diagonal \(d_1,\dots,d_n\).
Page: 005
Chapter: 1
Section: 3
Variables: \(n\in\mathbb N\),
\(d_1,\dots,d_n\in\mathbb Q\).
Notation: \(diag(d_1,\dots,d_n)\)
Index: 14

Name: A \(T\)-vector(matrix)
Definition: a vector(matrix) whose entries belongs to \(T\).
Page: 006
Chapter: 1
Section: 3
Variables: \(T\subseteq\mathbb Q\).

Name: A polyhedron
Definition: The set of points satisfying all linear inequalities in \(S\), for \(S\) a finite set of linear inequalities.
Page: 006, 88
Chapter: 1, 7
Section: 3, 1, 2
Index: , 1, 1b
Kind: , Cor,
Definition2: The sum of a polytope and of a polyhedral cone

Name: A lattice point
Definition: A vector of integer coordinates.
Page: 006
Chapter: 1
Section: 3
Extra: intégral véctor

Name: An \(1/k\)-integral vector/matrix
Definition: A vector/matrix whose all elements belongs to \(1/k\mathbb Z\).
Page: 006
Chapter: 1
Section: 3
Variables: \(k\in\mathbb N\).

Name: The incidence vector of \(T\) in \(S\)
Definition: The function sending \(T\) to 1 and \(S\setminus T\) to \(0\).
Page: 006
Chapter: 1
Section: 3
Variables: \(T\subseteq S\) sets.
Notation: \(\mathcal X_T\)
Name2: characteristic vector of \(T\) in \(S\)

Name: The support of \(v\)
Definition: the set of coordinates at which \(v\) is nonzero
Page: 006
Chapter: 1
Section: 3
Variables: \(v\) a vector

Name: The affine hull of a set \(X\) of vectors
Definition: \[\{\sum_{i=1}^t \lambda_i x_i\mid t\ge1, x_1,\dots,x_t\in X; \lambda_1,\dots,\lambda_t\in\mathbb R; \sum_{i=1}^t \lambda_i=1\}.\]
Page: 006, 100
Chapter: 1, 8
Section: 3, 2
Variables: \(m\in\mathbb N\), \(X\subseteq \mathbb Q^m\).
Definition2: \(\{x\mid A^=x=b^=\}\)
Definition3: \(\{x\mid A^=x\le b^=\}\)
Abbreviation: aff.hull \(X\)

Name: Convex set
Definition: A set \(X\subseteq \mathbb Q^m\) such that for all \(0\le l\le 1\), \(lx+(1-l)y\in C\).
Page: 006
Chapter: 1
Section: 3
Variables: \(m\in\mathbb N\).

Name: The linear hull of \(X\) of vectors
Definition: \[\left\{\sum_{i=1}^t \lambda_i x_i\mid t\ge0, x_1,\dots,x_t\in X; \lambda_1,\dots,\lambda_t\in\mathbb R\right\}.\]
Page: 006
Chapter: 1
Section: 3
Variables: \(m\in\mathbb N\)
\(X\subseteq \mathbb Q^m\).
Abbreviation: lin.hull \(X\)

Name: The cone generated by \(X\)
Definition: \[\left\{\sum_{i=1}^t \lambda_i x_i\mid t\ge0, x_1,\dots,x_t\in X; \lambda_1,\dots,\lambda_t\ge 0\right\}.\]
Page: 006
Chapter: 1
Section: 3
Variables: \(m\in\mathbb N\),
\(X\subseteq \mathbb Q^m\).
Abbreviation: cone \(X\)
Extra: hull
Intuition: The smallest convex cone containing \(X\)

Name: A (convex) cone
Definition: A subset of \(\mathbb Q^m\) which is closed under multiplication by positive rationals and under addition.
Page: 007
Chapter: 1
Section: 3
Variables: \(m\in\mathbb N\),
\(X\subseteq \mathbb Q^m\).

Name: A concave function
Definition: \(-f\) is convex.
Page: 007
Chapter: 1
Section: 3
Definition2: \(f(\lambda x+(1-\lambda)y)\ge\lambda f(x)+(1-\lambda)f(y)\) whenever \(x,y\in S\) and \(0\le\lambda\le1\).
Example2: A function \(f:S\to\mathbb Q\) defined on a convex set, such that

Name: Pivoting over the pivot element \((1,1)\)
Definition: Replacing \(A\) by the matrix \[\left[\begin{array}{ll}-\alpha^{-1}&\alpha^{-1}b\\\alpha^{-1}c&D-\alpha^{-1}cb \end{array}\right].\]
Page: 007
Chapter: 1
Section: 3
Variables: \(A=\left[\begin{array}{ll}\alpha& b\\c&D \end{array}\right]\) a matrix with
\(\alpha\) a scalar,
\(b\) a row vector,
\(c\) a column vector
\(D\) a matrix.
Assuming: \(\alpha\ne0\),

Smaller0: the area of the parallelepiped spanned by \(b_1,\dots,b_m\)
Greater0: \(\sqrt{det B^TB}\)
Page: 007
Chapter: 1
Section: 3
Variables: \(b_1,\dots,b_m\) are column vectors in \(\mathbb R^n\)
\(B\) is the \(n\times m\)-matrix with columns \(b_1,\dots,b_m\)
Kind: (26)
Smaller to greater: equals
Hide middle: yes

Smaller0: \(\sqrt{det B^TB} \)
Greater0: \(\Pi_{i=1}^m\parallel b_i\parallel\)
Page: 007
Chapter: 1
Section: 3
Variables: \(b_1,\dots,b_m\) be column vectors in \(\mathbb Q^n\)
\(B\) is the \(n\times m\)-matrix with columns \(b_1,\dots,b_m\).
Smaller to greater: \(\le\)
Greater to smaller: \(\ge\)

Smaller0: \(\sqrt{det \left(b_1,\dots,b_{m-1},b_m\right)^T\left(b_1,\dots,b_{m-1}b_m\right)}\)
Greater0: \(\frac{|c^T b_m|}{\parallel c\parallel}\sqrt{det \left(b_1,\dots,b_{m}\right)^T \left(b_1,\dots,b_{m-1}\right)} \)
Page: 007
Chapter: 1
Section: 3
Variables: \(b_1,\dots,b_m\) be column vectors in \(\mathbb R^n\)
Let \(b_1,\dots,b_m\) be \(n\)-columns vectors
\(c\) be orthogonals to \(b_1,\dots,b_{m-1}\).
Smaller to greater: =

Smaller0: \(D\) is positive definite
Greater0: \(D=C^TC\) for some nonsingular matrix \(C\)
Page: 008
Chapter: 1
Section: 3
Variables: \(D\) a square \(\mathbb K\)-matrix
Smaller to greater: iff
Assuming: \(\mathbb K=\mathbb R\)
Greatest: \(x^TDx>0\) for each nonzero vector \(x\)

Name: Two vectors orthogonal relative to \(D\)
Definition: Two elements \(c,d\in\mathbb Q^m\) such that \(c^TDd=0\).
Page: 008
Chapter: 1
Section: 3
Variables: \(m\in\mathbb N\)
\(D\) an inner product of \(\mathbb Q^m\).

Name: The norm defined by \(D\)
Definition: \(c\mapsto\sqrt{c^T Dc}\).
Page: 008
Chapter: 1
Section: 3
Variables: \(m\in\mathbb Q^m\),
\(D\subseteq\mathbb Q^{m\times m}\).

Name: The ball of radius \(\epsilon\) with centre \(x\)
Definition: \(\{y\in\mathbb R^n\mid \parallel x-y\parallel\le \epsilon\text{ for some $x$ in $S$} \}\).
Page: 008
Chapter: 1
Section: 3
Variables: \(x\in \mathbb G^n\)
\(\epsilon>0\).
Notation: \(B(S,\epsilon)\)

Name: The ellipsoid of center \(z\)
Definition: \[\{x\mid(x-z)^TD^{-1}(x-z)\le 1\}.\]
Page: 008
Chapter: 1
Section: 3
Variables: \(z\in\mathbb R^n\)
\(D\) a positive definite matrix of order \(n\)
Notation: \(ell(z,D)\)

Name: A simple graph
Definition: A graph which does not have multiple edges.
Page: 009
Chapter: 1
Section: 4

Name: The line graph of \(G\)
Definition: The graph \((E,\{(v,v')\mid v\cap v'\ne\emptyset\})\).
Page: 009
Chapter: 1
Section: 4
Variables: For \(G=(V,E)\) an undirected graph.
Notation: \(L(G)\)

Definition: the total bipartite graph with 3 and 3 vertices.
Page: 009
Chapter: 1
Section: 4
Notation: \(K_{3,3}\)

Name: Well-characterized problem
Definition: A problem which belongs to NP and to Co-NP.
Page: 019
Chapter: 2
Variables: \(P\) a problem.

Name: A rational polyhedron
Definition: A polyhedron determined by rational linear inequalities.
Page: 6
Chapter: I
Section: 3
Name2: A polyhedral subset of \(\mathbb R^n\)

Name: A Positive definite square matrix
Definition: A symmetric square matrix whose eigenvalues all are positive
Page: 8
Chapter: 1
Section: 3

Name: The convex hull of \(X\)
Definition: The smallest convex set containing \(X\)
Page: 006
Chapter: 1
Section: 3
Variables: \(m\in\mathbb N\),
\(X\subseteq \mathbb Q^m\).
Definition2: \[\left\{\sum_{i=1}^t \lambda_i x_i\mid t\ge1, x_1,\dots,x_t\in X; \lambda_1,\dots,\lambda_t\ge 0, \sum \lambda_i=1\right\}\]
Abbreviation: conv.hull \(X\)
Extra: The compound interest in relaxing punctality 2. P 3
Linear and integer programming, Ch0, p 6
Real analysis, Pugh Ch 2.9, p 115

Name: The incidence matrix of \(\mathcal C\)
Definition: its rows are the incidence vectors of the sets in \(\mathcal C\).
Page: 006
Chapter: 1
Section: 3
Variables: \(S\) a set and \(\mathcal C\) a collection of subsets of a set \(S\).
Definition2: \[M_{T,s}=1\text{ if} s\in T,M_{T,s}=0\text{ if} s\not\in T\] for \(T\in\mathcal C,s\in S\).
Conjdef: The \(\mathcal C\times S\)-matrix \(M\) such that, equivalently