Title: Theory / Unimportant / CS / Algo / Linear and integer programming / Schrijver{ / 1 Linear Algebra
Tags: fromMath fromAlgorithm hasNotNewEffectReturnsMeaning hasSeenConjDef oldAlgoNewName

Smaller0: vectors \(x_1,\dots,x_t\)
Greater0: \(x=\sum\lambda_i x_i\) for certain \(\lambda_i\in F\)
Page: 028
Chapter: 3
Section: 1
Variables: \(m\in\mathbb N\),
\(F\) a field
\(A\subseteq F^{m\times m}\).
Index: 1a
Kind: Cor
Smaller to greater: iff
Hide middle: yes
Smaller1: \(Ax=0\)
Prefix Smaller: there exists
Connect Smaller0: such that

Smaller0: has a solution
Greater0: (for all \(y\in\mathbb K\), \(yA=0\) implies \(yb=0\))
Page: 028
Chapter: 3
Section: 1
Variables: \(m,n\in\mathbb N\),
\(\mathbb K\) being the rationals or reals
\(A\subseteq\mathbb K^{m\times n}\)
\(b\in\mathbb K^n\).
Index: 1b
Kind: Cor
Smaller to greater: iff
Hide middle: yes
Name: Fundamental theorem of linear algebra
Prefix Smaller: the system \(Ax=b\)
Name2: First Fredholm theorem/Fredholm's theorem of the alternatives

Smaller0: \(x_0\) is a solution to the system \(Ax=b\)
Greater0: \(Ax=b\)
Page: 028
Chapter: 3
Section: 1
Variables: \(m,n\in\mathbb N\),
\(\mathbb K\) being the rationals or reals
\(A\subseteq\mathbb K^{m\times n}\)
\(b\in\mathbb K^n\).
Index: 1ac
Kind: Cor
Hide middle: yes
Prefix Greater: there exists vectors \(x_1,\dots,x_t\) such that
Greater1: \(x=x_0+\sum\lambda_i x_i\) for certain rationals \(\lambda_1,\dots,\lambda_t\)
Connect Greater0: iff

Smaller0: \(x_0\) is a solution to the system \(Ax=b\)
Greater0: at most \(4n^2\phi\)
Page: 028
Chapter: 3
Section: 1
Variables: \(m,n\in\mathbb N\),
\(\mathbb K\) being the rationals or reals
\(A\subseteq\mathbb K^{m\times n}\)
\(b\in\mathbb K^n\).
Index: ac
Kind: Cor
Hide middle: yes
Prefix Greater: the size of the \(x_i\) is
Smaller1: \(A\) and \(b\) are rationals and each row of the matrix \([A b]\) has size at most \(\phi\)

Smaller0: \(Ax=b\) implies \(cx=\delta\)
Greater0: there is a row vector \(y\) such that \(yA=c\) and \(yb=\delta\)
Page: 029
Chapter: 3
Section: 1
Variables: \(m,n\in\mathbb N\),
\(\mathbb K\) being the rationals or reals
\(A\subseteq\mathbb K^{m\times n}\)
\(b\in\mathbb K^n\).
\(c\in\mathbb K^m\),
\(\delta\in\mathbb K\).
Index: d
Kind: Cor
Smaller to greater: iff
Hide middle: yes
Assuming: the system \(Ax=b\) has a solution

Question: The size of \(\text{det }A\) is
Answer: less than \(2\sigma\).
Page: 029
Chapter: 3
Section: 2
Variables: \(m\in\mathbb N\),
\(A\subseteq\mathbb Q^{m\times m}\) of size \(\sigma\)
Kind: Theo

Question: The size of \(A^{-1}\) is
Answer: less than \(3\sigma\).
Page: 030
Chapter: 3
Section: 2
Variables: \(m,n\in\mathbb N\)
\(A\subseteq\mathbb Q^{m\times n}\)
\(b\in\mathbb Q^m\)
Index: b
Kind: Cor
Extra: (\(2\sigma\) for the determinants, plus a \(\sigma\) for the cofactors)

Page: 030, 32
Implementation: Create matrix \(A'=\left[\begin{array}{ll}B&C\\0&0\end{array}\right]\) where \(B\) is diagonal matrix with 1 on the diagonal, and \(b'\), such that \(Ax=b\) is equivalent to \(A'x=b'\)
By induction, if there is at moste one non zero line, it is done.
Otherwise, reorder line to obtain \(A^1x=b^1\), with \(A_{1,1}^1\ne0\).
Add to line \(j\) \(-A_{j,1}^1/A_{1,1}^1\) times line 1.
Apply recursively without first line and first column, to obtain \(\left[\begin{array}{ll}B^2&C^2\\0&0\end{array}\right]\) and \(\beta^2\),
Add to line 1, \(-A_{1,k}\) times line \(k\)
Section: 2, 3
Chapter: 3
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}\)
\(b=\left(\begin{array}{l}\beta_1\\ \vdots\\ \beta_m\end{array}\right)\in\mathbb Q^m\).
Name: Gaussian algorithm
Time complexity: \(O(n^3)\) arithmetic operation
Returns: Does \(Ax=b\) have a solution
Index: c
Kind: Cor

Question: There exists \(x\) such that \(Ax=b\) implies
Answer: a polynomially-bounded \(x\) exists satisfing this equality
Page: 030
Chapter: 3
Section: 2
Variables: \(m,n\in\mathbb N\)
\(A\subseteq\mathbb Q^{m\times n}\)
\(b\in\mathbb Q^m\)
Index: 2c
Kind: Cor

Question: \(Ax=b\) have no solution implies
Answer: there is a polynomial sized \(y\) with \(yA\) integral and \(yb\) not an integer.
Page: 030
Chapter: 3
Section: 2
Variables: \(m,n\in\mathbb N\)
\(A\subseteq\mathbb Q^{m\times n}\)
\(b\in\mathbb Q^m\)
Index: 2c
Kind: Cor
Extra: 5.2ab

Page: 36
Implementation: \(x_0=b\) and \(x_{k+1}:=(I-A)x_k+b\)
Section: 1
Chapter: 4
Variables: \(m\in\mathbb N\),
\(A\subseteq\mathbb Q^{m\times m}\)
\(b\in\mathbb Q^m\).
Name: Jacobi iteration method
Returns: A sequence converging to a solution of \(Ax=b\)
Assuming: \(A\) is non singular and 1 on the diagonal

Name: A linear hyperplane of \(F^n\)
Definition: (The set of \(x\in F^n\) such that \(ax=0\)) for some nonzero row vector \(a\in F^n\)
Page: 27
Chapter: 3
Section: 1
Variables: \(F\) a field

Name: A linear subspace
Definition: the intersection of finitely many linear hyperplanes
Page: 27
Chapter: 3
Section: 1
Variables: \(F\) a field,
\(n\in\mathbb N\)
Context: \(F^n\)
Kind: Theo
Definition2: generated by finitely many vectors
Conjdef: A non empty set, equivalently
Definition3: set of \(x\) such that \(Ax=0\) for some matrix \(A\)
Definition4: set of \(Cy\) for some matrix \(C\) fixed

Name: A fundamental system of solution of \(Ax=0\)
Definition: A base of the space \(Ax=0\)
Page: 28
Chapter: 3
Section: 1
Variables: \(F\) a field,
\(n\in\mathbb N\)
\(A\) a \(n\times n\) matrix

Definition: \(1+\lceil\log_2(|p|+1)\rceil+\lceil\log_2(|q|+1)\rceil\)
Page: 29
Chapter: 3
Section: 2
Variables: \(\frac pq\) rational in irreduccible form
Notation: \(\mathrm{size}(\frac pq)\)

Definition: \(n+\sum_{i=1}^n\mathrm{size}(c_i)\)
Page: 29
Chapter: 3
Section: 2
Variables: \(c\in\mathbb Q^n\)
Notation: \(\mathrm{size}(c)\)

Definition: \(n+\sum_{i=1}^{mn}\mathrm{size}(\alpha_{ij})\)
Page: 29
Chapter: 3
Section: 2
Variables: \(A=(\alpha_{ij})_{i=1,j=1}^{m,n}\)
Notation: \(\mathrm{size}(A)\)

Question: the set of solutions of \(\left(\begin{array}{lll}\alpha_{1,1}&\dots&\alpha_{1,n}\\\vdots&&\vdots\\\alpha_{j,1}&\dots&\alpha_{j,n}\\\vdots&&\vdots\\\alpha_{i,1}&\dots&\alpha_{i,n}\\\vdots&&\vdots\\\alpha_{m,1}&\dots&\alpha_{m,n}\end{array}\right)\left(\begin{array}{l}x_1\\ \vdots\\ x_n\end{array}\right)=\left(\begin{array}{l}\beta_1\\ \vdots \\ \beta_i\\\vdots\\ \beta_j\\ \vdots\\ \beta_m\end{array}\right)\)
Answer: is the same than the one of
the set of solutions of \(\left(\begin{array}{lll}\alpha_{1,1}&\dots&\alpha_{1,n}\\\vdots&&\vdots\\\alpha_{i,1}&\dots&\alpha_{i,n}\\\vdots&&\vdots\\\alpha_{j,1}&\dots&\alpha_{j,n}\\\vdots&&\vdots\\\alpha_{m,1}&\dots&\alpha_{m,n}\end{array}\right)\left(\begin{array}{l}x_1\\ \vdots\\ x_m\end{array}\right)=\left(\begin{array}{l}\beta_1\\ \vdots \\ \beta_i\\\vdots\\ \beta_j\\ \vdots\\ \beta_m\end{array}\right)\)
Page: 32
Chapter: 3
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}\)
\(b=\left(\begin{array}{l}\beta_1\\ \vdots\\ \beta_m\end{array}\right)\in\mathbb Q^m\).
\(1\le i<j\le m\)

Question: the set of solutions of \(\left( \begin{array}{lllllll}\alpha_{1,1}&\dots&\alpha_{1,j}&\dots&\alpha_{1,i}&\dots&\alpha_{1,n}\\\vdots&&&&&&\vdots\\\alpha_{m,1}&\dots&\alpha_{m,j}&\dots&\alpha_{m,i}&\dots&\alpha_{m,n}\\\end{array}\right)\left(\begin{array}{l}x_1\\ \vdots\\ x_j\\\vdots\\ x_i\\ \vdots\\ x_n\end{array}\right)=\left(\begin{array}{l}\beta_1\\ \vdots \\\beta_m\end{array}\right)\)
Answer: is the same than the one of \(\left(\begin{array}{lllllll}\alpha_{1,1}&\dots&\alpha_{1,i}&\dots&\alpha_{1,j}&\dots&\alpha_{1,n}\\\vdots&&&&&&\vdots\\\alpha_{m,1}&\dots&\alpha_{m,i}&\dots&\alpha_{m,j}&\dots&\alpha_{m,n}\\\end{array}\right)\left(\begin{array}{l}x_1\\ \vdots\\ x_i\\\vdots\\ x_j\\ \vdots\\ x_n\end{array}\right)=\left(\begin{array}{l}\beta_1\\ \vdots\\ \beta_m\end{array}\right)\)
Page: 32
Chapter: 3
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}\)
\(b=\left(\begin{array}{l}\beta_1\\ \vdots\\ \beta_m\end{array}\right)\in\mathbb Q^m\).
\(1\le i<j\le m\)

Page: 33
Implementation: Apply Gaussian elimination and compute the number of nonzero on the diagonal
Section: 3
Effect: The rank of \(A\)
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}\)
Time complexity: \(O(n^3)\) arithmetic operation
Index: a (ii)
Kind: Cor

Page: 33
Implementation: Apply the Gaussian algorithm to \([AI]\) to obtain \([\Delta C]\) with \(\Delta\) diagonal matrix. Takes \(\Delta^{-1}C\)
Section: 3
Effect: The inverse of \(A\)
Variables: \(A=\left(\begin{array}{lll}\alpha_{1,1}&\dots&\alpha_{1,n}\\\vdots&&\vdots\\\alpha_{n,1}&\dots&\alpha_{n,n}\end{array}\right)\subseteq\mathbb Q^{m\times n}\)
Time complexity: P
Index: a (iii)
Kind: Cor

Question: The determinant of \(A\)
Answer: P
Page: 33
Chapter: 3
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}\)
Index: a (i)
Kind: Cor
Extra: todo

Page: 33
Implementation: Apply the Gaussian algorithm to \([AI]\) to obtain \([\Delta C]\). Accept if \(\Delta\) has no zero on the diagonal.
Section: 3
Effect: whether the lines are linearly independant
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}\)
Time complexity: P
Index: a (iv)
Kind: Cor

Page: 33
Section: 3
Chapter: 4
Effect: The determinant of \(A\)
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}\)
Time complexity: P
Index: a(i)
Kind: cor
Extra: todo