Homework 5
This homework covers the material from lectures 17 to 21
Due date: April 12th.
LaTeX template for homework 5, in case you want to write it in LaTeX.
Required Exercises
Remember that you are only required to turn in 5 out of the 6 exercises below.
Problem 1 - Fast Modular Composition (20 points)
Let $g = h = x^3 + 2x^2 + 3x + 4$ and $f = x^4 -1$ be polynomials over $\mathbb{F}_5[ x ]$. Use the fast modular composition algorithm to compute $g(h) \bmod f$.
Problem 2 - proving that $\omega_{det} = \omega_{mult}$ (20 points)
Given a matrix $A \in \mathbb{F}^{N \times N}$ where $N = 2^k$, prove that one can compute $\det(A)$ in time $O(n^\omega)$, where $\omega$ is the matrix multiplication exponent. You can assume that any matrix that you need to invert in the process is invertible.
Optional question: how would you remove the assumption given above?
Problem 3 - linear recurrence relations and minimal polynomials (20 points)
- Determine a recurrence relation and sufficiently many initial values of the sequence $(a_i)_{i \in \mathbb{N}} \in \mathbb{Q}^\mathbb{N}$ if $h(x) = \sum_{i \geq 0} a_i x^i$ is
$$ h(x) = \dfrac{x^2+x}{x^3-x-1} $$
- Compute the minimal polynomial of the sequence $1, 3, 4, 7, 11, 18, 29, 47, \ldots$ of rational numbers, given that the recursion order is at most 4. Give the next 5 elements of the sequence.
Problem 4 - using linear recurrent relations to decide singularity (20 points)
Let $A \in \mathbb{Q}^{n \times n}$ be a square matrix. Give a probabilistic “black box” algorithm which performs at most $O(c(A) \cdot n + n^2)$ field operations and decides whether $A$ is singular. Your algorithm should return the correct answer with probability at least $2/3$.
Problem 5 - Toeplitz matrices (20 points)
A Toeplitz matrix $A \in \mathbb{F}^{n \times n}$ is a matrix whose entries are constant along the diagonals, for instance:
$$ A =
\begin{pmatrix}
3 & 2 & 1 \\
4 & 3 & 2 \\
5 & 4 & 3
\end{pmatrix} $$
-
Prove that you can multiply an $n \times n$ Toeplitz matrix by an $n \times 1$ vector in $O(M(n))$ operations, where recall that $M(n)$ is the number of operations needed to multiply two polynomials of degree $\leq n$.
-
Prove that given $\beta \in \mathbb{F}$, you can compute $\beta^0, \beta^1, \beta^4, \beta^9, \ldots, \beta^{(n-1)^2}$ in $O(n)$ operations in $\mathbb{F}$.
Hint: think of $(i+1)^2 - i^2$
- Given a polynomial $f(x) \in \mathbb{F}[ x ]$ with degree $< n$, and $\alpha \in \mathbb{F}$, let us now see how to compute $f(\alpha^0), f(\alpha^1), \ldots, f(\alpha^{n-1})$, assuming that we know $\beta \in \mathbb{F}$ such that $\beta^2 = \alpha$ (that is, a square root of $\alpha$).
Let $f(x) = f_0 + f_1 x + \ldots + f_{n-1} x^{n-1}$ What is the matrix of the operation
$$ (f_0, \ldots, f_{n-1}) \mapsto (f(\alpha^0), \ldots, f(\alpha^{n-1}))? $$
Describe this matrix by showing what the $(i,j)$ entry of this matrix is.
- Using the fact that $ij = \dfrac{(i+j)^2 - i^2 - j^2}{2}$, rewrite the matrix from the previous part as a product of 3 matrices, involving a particular Toepliz matrix.
Suggestion: write this down for $n = 3$ first
- Show that you can compute $f(\alpha^0), f(\alpha^1), \ldots, f(\alpha^{n-1})$ in $O(M(n))$ operations.
Problem 6 - Wiedemann’s algorithm (20 points)
Implement, in Maple or Macaulay2, the Wiedemann algorithm (as we saw in class) for solving a sparse linear system. As input, the algorithm will take:
- an integer $n$ (size of the matrix),
- a prime integer $p$ (we work in $\mathbb{F}_p$),
- $n$ integers in ${0, \ldots , p − 1}$ (this is the right-hand vector $b$)
- a sequence of triples $i, j, a_{i,j}$, with $i, j \in {1, . . . , n}$ and $a_{i,j} \in {0, . . . , p − 1}$ (these are the non-zero entries in the matrix $A$).
The output is a vector $x$ such that $Ax = b.$ The algorithm is randomized, but if something goes wrong, you can detect it; in this case, return “error”, or throw an exception, or something along these lines. We will give input matrices, with the same format as above. Your code should pass the inputs of size up to $10$ and $100$ with $p = 9001$; the input matrix with coefficients modulo p = 2 is more challenging (there is a good chance the algorithm will fail).
Input matrices for $p = 9001$: size 10, size 100, size 1000, size 10000
Input matrices for $p = 2$ (do it at your own risk): size 50
You have to implement the algorithm for discovering a recurrence for a given sequence, but you do not have to reimplement polynomial multiplication or division. Remember, all computations must be done modulo $p$.
Practice Problems
You are not required to submit the solution to these problems, but highly encouraged to attempt them for your own knowledge sake. :)
Problem 1
Let your base field be $\mathbb{F}_5$ and consider
$$
A =
\begin{pmatrix}
1 & 2 & 3 \\
4 & 0 & 1 \\
1 & 3 & 1
\end{pmatrix}, \ \ \
b =
\begin{pmatrix}
0 \\
1 \\
2 \\
\end{pmatrix}
$$
Compute $A^{-1}b$ using Wiedemann’s algorithm.