Question

Use the familiar formula \(\operatorname{det} A=\sum_{\sigma \in S_{n}} \operatorname{sign}(\sigma) \cdot a_{1 \sigma(1)} \cdots a_{n \sigma(n)}\) for the determinant of a square matrix \(A \in \mathbb{Z}^{n \times n}\), where \(S_{n}\) is the symmetric group of all \(n\) ! permutations of \(\\{1, \ldots, n\\}\) (Section 25.1), to derive an upper bound on \(|\operatorname{det} A|\) in terms of \(n\) and \(B=\max _{1 \leq i, j \leq n}\left|a_{i j}\right|\). Compare this to the Hadamard bound, and tabulate both bounds and their ratio for \(1 \leq n \leq 10\).

Short answer

The derived upper bound is \( n! \cdot B^n \). The ratio with Hadamard's is \( \frac{n!}{n^{n/2}} \).

Step-by-step solution

Understanding the Determinant Formula

The determinant of a matrix \(A\) is given by the formula \(\operatorname{det} A=\sum_{\sigma \in S_{n}}\operatorname{sign}(\sigma) \cdot a_{1 \sigma(1)} \cdots a_{n \sigma(n)}\). Here, \(S_n\) is the set of all permutations of \(\{1, \ldots, n\}\). Each term in the summation involves the product of \(n\) elements from the matrix, corresponding to a permutation of the indices.

Estimating Each Term of the Determinant

Each term in the determinant formula is a product of \(n\) matrix elements. The absolute value of each term can be at most \(|a_{1,\sigma(1)}| \times |a_{2,\sigma(2)}| \times \cdots \times |a_{n,\sigma(n)}|\). Since we have defined \(B\) as the maximum absolute value of the elements \(a_{ij}\), each term is bounded by \(B^n\).

Counting the Number of Permutations

The set \(S_n\) contains \(n!\) permutations. The determinant is a sum over these \(n!\) permutations, so it has \(n!\) terms.

Deriving Upper Bound on |det A|

The absolute value of \(\operatorname{det} A\) is bounded by the sum of the absolute values of all terms: \[|\operatorname{det} A| \leq \sum_{\sigma \in S_{n}} |a_{1\sigma(1)}| \cdots |a_{n\sigma(n)}| \leq n! \cdot B^n\]This is the derived upper bound on \(|\operatorname{det} A|\).

Comparing with Hadamard Bound

The Hadamard bound states that \[|\operatorname{det} A| \leq \prod_{i=1}^{n} \sqrt{\sum_{j=1}^{n} a_{ij}^2}\]For a matrix where the maximum absolute value of elements is \(B\), the Hadamard bound simplifies to \(n^{n/2} \cdot B^n\) in the worst case.

Tabulating the bounds for 1 ≤ n ≤ 10

Calculate both bounds for matrices of size \(n = 1, 2, \ldots, 10\) and compare. The derived bound is \(n! \cdot B^n\) while Hadamard's is \(n^{n/2} \cdot B^n\). The ratio is \(\frac{n!}{n^{n/2}}\). For each \(n\), compute these to complete the table.

Key concepts

Matrix Determinant

The determinant of a matrix is a special number that can be calculated from its elements. Specifically, for a square matrix \( A \) of order \( n \), the determinant is denoted as \( \operatorname{det}(A) \). The formula employed to calculate this determinant involves a summation over permutations:

• \( \operatorname{det} A = \sum_{\sigma \in S_{n}} \operatorname{sign}(\sigma) \cdot a_{1 \sigma(1)} \cdots a_{n \sigma(n)} \)

Here, \( S_n \) refers to the set of all permutations of \( \{1, 2, \ldots, n\} \). The term \( \operatorname{sign}(\sigma) \) captures whether a permutation is even or odd, affecting the sign of the term in the sum.
Each term in the determinant calculation is a product of \( n \) elements, chosen by permuting the indices, essentially capturing every possible way to pick elements, one from each row and distinct column. This expression allows us to analyze how the matrix behaves, particularly regarding linear transformations and the volumes computed in geometric contexts. Understanding this concept is crucial in fields like geometry and physics where matrices are used to represent systems of linear equations.

Permutation in Linear Algebra

Permutations are a central concept in linear algebra, playing a crucial role in the calculation of determinants. A permutation of \( n \) elements is one of its possible arrangements or orders. For example, with two elements \( \{1, 2\} \), the permutations are \( \{1, 2\} \) and \( \{2, 1\} \).
In mathematical terms, for a set of \( n \) elements, the group of all permutations, denoted as \( S_n \), contains \( n! \) permutations.

• "\( n! \)" refers to \( n \) factorial, which is the product of all positive integers up to \( n \) (e.g., \( 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120 \)).

For determinant computation, each permutation represents a way to select one element from each row while ensuring no two elements are from the same column. This is why permutations are crucial—they ensure that the entire matrix is considered in an orderly and exhaustive manner. Additionally, the sign of a permutation, either +1 or -1, indicates whether the permutation is even or odd. This sign influences whether a term is added or subtracted in calculating the determinant.

Hadamard Bound

The Hadamard bound provides a crucial upper limit to the value of a determinant. In essence, it gives us a way to estimate how large the determinant of a matrix can be solely based on its entries. Given an \( n \times n \) matrix \( A \) with entries having a maximum absolute value \( B \), the Hadamard bound is mathematically expressed as:
\[ |\operatorname{det} A| \leq \prod_{i=1}^{n} \sqrt{\sum_{j=1}^{n} a_{ij}^2} \]In simpler terms, it can be shown that if we are primarily concerned with the maximum size each entry can take, this bound simplifies to:

• \( n^{n/2} \cdot B^n \)

This bound is tighter than the derived bound \( n! \cdot B^n \), especially for larger \( n \). By comparing it to the derived formulae from earlier steps, we can evaluate how realistic our initial upper estimates are and refine our bounds. The Hadamard bound highlights how intricacies of matrix structure can cap the determinant size, making it a valuable tool for researchers dealing with complex matrix systems and ensuring computational accuracy without performing exhaustive calculations.