Question

Let \(F\) be a field, \(n \in \mathbb{N}_{>0}\), and \(A=\left(a_{i j}\right)_{1 \leq i, j \leq n} \in F[x]^{n \times n}\) a square matrix with polynomial entries. Moreover, let \(m=\max \left\\{\operatorname{deg} a_{i j}: 1 \leq i, j \leq n\right\\}\). (i) Find a tight upper bound \(r \in \mathbb{N}\) on \(\operatorname{deg}(\operatorname{det} A)\) in terms of \(m\) and \(n\). (ii) Describe an algorithm for computing \(\operatorname{det} A\) using a small primes modular approach if the field \(F\) has more than \(r\) elements. Hint: Choose linear moduli. How many operations in \(F\) does your algorithm use (in terms of \(n\) and \(m\) )? (iii) Use your algorithm to compute the determinant of the matrix $$ A=\left(\begin{array}{ccc} -x+1 & 0 & 2 \\ x & x+1 & 2 x \\ 2 x & 3 x+1 & x \end{array}\right) \in \mathbb{F}_{7}[x]^{3 \times 3} $$ (iv) Find a tight upper bound on \(\operatorname{deg}(\operatorname{det} A)\) in terms of the maximal degrees \(m_{i}\) in the \(i\) th row of \(A\) for \(1 \leq i \leq n\). (Sometimes, this bound or the corresponding bound arising from the maximal column degrees is better than the bound from (i).) (v) Using the bound from (iv), compute the determinant of $$ A=\left(\begin{array}{ccc} x-1 & x-2 & x-3 \\ 2 x+1 & 2 x+3 & 2 x-2 \\ x^{2}-1 & x^{2}+x+1 & (x-1)^{2} \end{array}\right) \in \mathbb{F}_{7}[x]^{3 \times 3} $$

Short answer

(i) Upper bound is \( n \cdot m \). (ii) Use small primes and modular arithmetic, scaling \( O(n^3m) \). (iii) \( \det(A) = 6x^3 + 6x^2 + x \mod 7 \). (iv) Use row degree sum, \( \sum m_i \). (v) \( \det(A) = -x^3 + 4x^2 - x + 3 \mod 7 \).

Step-by-step solution

Upper Bound on Degree of Determinant (i)

For a polynomial matrix \( A \), the degree of the determinant can be determined by considering the permutations in its expansion. If the highest degree of any entry \( a_{ij} \) is \( m \), then the maximum possible degree of the determinant of an \( n \times n \) matrix is \( n \cdot m \). Thus, the tight upper bound on \( \deg(\det A) \) is \( n \cdot m \).

Algorithm for Computing the Determinant (ii)

Use the modular method by selecting primes larger than the degree bound \( r = n \cdot m \). Compute the determinant modulo these primes in the field \( F \), and use the Chinese remainder theorem to recover \( \det A \) over \( \mathbb{F}_7[x] \). This technique involves performing polynomial arithmetic, making the algorithm's complexity approximately \( O(n^3m) \).

Compute Determinant Using Algorithm (iii)

The matrix \((A)\) in \( \mathbb{F}_{7}[x] \) is:\[A = \begin{pmatrix} -x+1 & 0 & 2 \ x & x+1 & 2x \ 2x & 3x+1 & x \end{pmatrix}\].Compute \( \det(A) \) over the field \( \mathbb{F}_7 \). Use expansion by minors to evaluate the determinant modulo each chosen prime, then combine results using Chinese Remainder Theorem. Result is \( \det(A) = -x^3 - x^2 + x \equiv 6x^3 + 6x^2 + x \mod 7 \).

Upper Bound Using Maximal Row Degrees (iv)

The degree bound can be refined using the row-wise maximal degrees. Assume \( m_i \) is the highest degree entry in row \( i \). Here, the upper bound is \( \sum_{i=1}^{n} m_i \). This might be tighter than \( n \cdot m \) when the degrees vary significantly across rows.

Compute Determinant Using Row Degree Bound (v)

For the matrix \( A \) given, determine row degrees:- Row 1: \((-1, -2, -3)\) each have degree 1.- Row 2: \((2x+1, 2x+3, 2x-2)\) each have degree 1.- Row 3: \((x^2-1, x^2+x+1, (x-1)^2)\) each have degree 2.The bound is thus \( 1 + 1 + 2 = 4 \). Calculate determinant using expansion or cofactors, tallying up to this bound, yielding \( \det(A) = -x^3 + 4x^2 - 7x + 3 \equiv -x^3 + 4x^2 - x + 3 \mod 7 \).

Key concepts

Upper Bound on Degree

The upper bound on the degree of the determinant of a polynomial matrix is a crucial concept in understanding polynomial matrices. For an \(n \times n\) matrix \(A\) with entries that are polynomials having a maximum degree \(m\), determining the degree of \(\det(A)\) involves considering all permutations in its determinant expansion. In terms of the upper bound, the maximum degree that \(\det(A)\) can reach is the result of multiplying the size of the matrix \(n\) by \(m\), hence \(n \cdot m\). This upper bound is 'tight' because it's the highest degree the determinant can realistically attain after accounting for all matrix permutations. This approach is highly beneficial for creating algorithms that need to estimate processing time or memory space required in matrix operations involving polynomials.

Modular Arithmetic

Modular arithmetic plays a significant role in computing the determinant of matrices with polynomial entries. This system of arithmetic confines numbers within a defined set by using a modulus. In the context of polynomial matrices, applying modular arithmetic allows us to simplify computations significantly by working with numbers as remainders upon division by a chosen modulus.
This reduction helps in managing complex polynomial operations, offering easier computational paths and allowing for secure and efficient calculations across different algebraic fields. For example, when dealing with coefficients, modular arithmetic helps in reducing large coefficients by computing them modulo a prime, ultimately simplifying polynomial algebra tasks.

Chinese Remainder Theorem

The Chinese Remainder Theorem is a powerful mathematical tool in calculations involving modular arithmetic, particularly within matrix algebra. When dealing with polynomial matrices, once each determinant is reduced modulo a series of prime numbers, the Chinese Remainder Theorem provides a method to piece these modular results back together.
This theorem ensures that, given several congruences with pairwise coprime moduli, there exists a solution that is unique modulo the product of these moduli.

• First, compute the determinant modulo several small primes.
• Second, use the Chinese Remainder Theorem to combine these results into a final
  determinant over the original polynomial field.

This combination process is crucial in ensuring that the final result is accurate and consistent within the constraints of modular spaces.

Matrix Algebra

Matrix algebra provides the foundational operations and properties necessary for handling polynomial matrices. When computing the determinant of a polynomial matrix, it extends basic matrix concepts such as permutations and cofactor expansions. Matrix algebra enables various manipulative techniques like row reduction and expansion by minors to be employed.
By understanding properties of matrices, such as invertibility and adjugate matrices, complex algebraic operations become more manageable, and solving polynomial matrix equations becomes feasible. These algebraic operations, therefore, drive the computational algorithms essential for handling polynomial matrices efficiently in various applications across fields of science and engineering.

Small Primes Approach

The small primes approach simplifies complex polynomial determinant calculations by choosing small prime numbers that are larger than the determined degree bound of the polynomial matrix's determinant. This method involves key steps:

• Choose small prime numbers to use as moduli.
• Compute the determinant of the matrix modulo each chosen prime, simplifying operations by working with smaller numbers.

These primes act as the base for modular arithmetic calculations and ensure that the individual results can be seamlessly pieced together using the Chinese Remainder Theorem. Employing this technique reduces computational overhead and ensures that solutions are efficient, especially when dealing with large polynomial matrices, making it a preferred choice in mathematical computations involving determinant evaluations.