on Sylvester's determinantal identity and Schweinsian expansion

Overview

This post examines the classical algebraic theory of determinants through the lens of Sylvester’s Determinantal Identity (Sylvester, 1851) and the Schweinsian Expansion [@schweins1825theorie]. These results provide the foundational framework for modern fraction-free algorithms, recursive least squares, and sequence acceleration techniques. We explore their derivation via Schur complements and their implications for numerical analysis.

🏷️ Sylvester’s Determinantal Identity

Sylvester’s identity is a fundamental result in multilinear algebra that relates the determinant of a large matrix to the determinants of its “bordered” minors. It serves as a bridge between local submatrix properties and global determinantal invariants.

The Formal Statement

Let $A\in {\mathbb{R}}^{n\times n}$ and let $M=A_{1\dots k}$ be its $k\times k$ leading principal submatrix. For indices $i,j$ such that $k<i,j\le n$, define the bordered minor $a_{ij}^{(k)}$ as:

$$a_{ij}^{(k)}=\det \left(\begin{array}{cc}M& b_j\\ c_i^T& a_{ij}\end{array}\right)$$

where $b_j$ is the $j$-th column of the top-right block and $c_i^T$ is the $i$-th row of the bottom-left block.

Sylvester’s Identity states that the determinant of the $(n-k)\times (n-k)$ matrix formed by these minors is proportional to the original determinant:

$$\det (A)\cdot (\det (M){)}^{n-k-1}=\det {\left(a_{ij}^{(k)}\right)}_{i,j=k+1}^n$$

Proof via Schur Complements

The most insightful proof of this identity utilizes the Schur Complement. Consider the block decomposition of $A$ into a $k\times k$ leading principal submatrix $M$ and its surrounding blocks:

$$A=\left(\begin{array}{cc}M& B\\ C& D\end{array}\right)$$

By the fundamental property of block matrices, the determinant admits the factorization $\det (A)=\det (M)\det (S)$, where $S=D-C{M}^{-1}B$ is the Schur complement of $M$ in $A$.

A crucial observation is that the entries $s_{ij}$ of the Schur complement correspond precisely to the normalized bordered minors. Specifically, for indices $i,j>k$, the $(i-k,j-k)$-th entry is given by $a_{ij}-c_i^T{M}^{-1}{b}_j$. By applying Cramer’s rule to the augmented system $\left(\begin{array}{cc}M& b_j\\ c_i^T& a_{ij}\end{array}\right)$, we find that:

$$s_{ij}=\frac{a_{ij}^{(k)}}{\det (M)}$$

Upon substituting this entry-wise expression into the determinant of the Schur complement, we obtain:

$$\det (A)=\det (M)\det {\left(\frac{1}{\det (M)}{a}_{ij}^{(k)}\right)}_{i,j=k+1}^n$$

Since the matrix of bordered minors is of order $(n-k)$, the scalar factor $(\det (M){)}^{-1}$ is raised to the $(n-k)$-th power when pulled out of the determinant. This leads to the identity:

$$\det (A)=\det (M)\cdot \frac{1}{(\det (M){)}^{n-k}}\det \left(a_{ij}^{(k)}\right)$$

Rearranging the terms yields the final result: $\det (A)\cdot (\det (M){)}^{n-k-1}=\det \left(a_{ij}^{(k)}\right)$. ▮

🏷️ The Schweinsian Expansion

While Sylvester’s identity provides a “local” update rule for determinants, the Schweinsian Expansion [@schweins1825theorie] provides a “global” series for the ratio of two determinants. This is critical in applications where a basis is expanded iteratively, such as in polynomial interpolation or recursive filtering.

Schweins' Identity

Let $A_n$ denote the determinant $|a_1\dots a_n|$. For a vector $x$, the difference between ratios of successive orders is given by:

$$\frac{|a_1\dots a_{n}x|}{|a_1\dots a_n{a}_{n+1}|}-\frac{|a_1\dots a_{n-1}x|}{|a_1\dots a_{n-1}{a}_n|}=\frac{|a_1\dots a_{n-1}{a}_{n}x|\cdot |a_1\dots a_{n-1}{a}_{n+1}|}{|a_1\dots a_n{a}_{n+1}|\cdot |a_1\dots a_n|}$$

Proof of Schweins' Identity

The proof of this identity is a masterful application of Sylvester’s Determinantal Identity to a specifically constructed composite determinant.

Consider the determinant of the $(n+1)\times (n+1)$ matrix formed by the columns $[a_1,\dots ,a_{n-1},a_n,a_{n+1}]$. By applying Sylvester’s identity with the leading principal submatrix $M=[a_1,\dots ,a_{n-1}]$, we can express the global determinant in terms of its $(n-1)$-th order condensation.

Specifically, let $D$ be a matrix where we have appended the vector $x$ as an additional column and row. By analyzing the difference of the ratios:

$$\Delta R=\frac{|a_1\dots a_{n}x|}{|a_1\dots a_n{a}_{n+1}|}-\frac{|a_1\dots a_{n-1}x|}{|a_1\dots a_{n-1}{a}_n|}$$

We can combine these terms over a common denominator $|a_1\dots a_n{a}_{n+1}|\cdot |a_1\dots a_n|$. The numerator of the resulting fraction becomes:

$$|a_1\dots a_{n}x|\cdot |a_1\dots a_n|-|a_1\dots a_{n-1}x|\cdot |a_1\dots a_n{a}_{n+1}|$$

This expression is precisely the expansion of the Desnanot-Jacobi identity (the $k=n-1$ case of Sylvester’s Identity) applied to the matrix $[a_1\dots a_{n-1},a_n,a_{n+1},x]$. Identifying the minors:

• $M_{1,n;1,n}$ corresponds to $|a_1\dots a_{n-1}|$
• $M$ corresponds to $|a_1\dots a_{n+1}x|$

The identity reveals that this numerator is equal to the product $|a_1\dots a_{n-1}{a}_{n}x|\cdot |a_1\dots a_{n-1}{a}_{n+1}|$. Dividing by the common denominator yields the Schweinsian result. ▮

🏷️ Insights into the Schweinsian Series

By summing these differences telescopically, we obtain the full Schweinsian Series:

$$\frac{|a_1\dots a_{n}x|}{|a_1\dots a_n{a}_{n+1}|}=\sum _{k=1}^n\frac{|a_1\dots a_{k-1}{a}_{k+1}\dots a_{n}x|\cdot |a_1\dots a_{k-1}{a}_k|}{|a_1\dots a_k|\cdot |a_1\dots a_{k-1}|}$$

Architectural Intuition

1. Discrete Taylor Series: The expansion can be viewed as a discrete analog of a Taylor series for determinantal quotients.
2. Interpolation Link: This identity is the algebraic core of the Aitken-Neville algorithm.
3. Connection to Divided Differences: In the limit, these ratios converge to Divided Differences, linking classical linear algebra directly to numerical approximation theory.

🏷️ Numerical Stability and Exact Computing

The professional significance of these identities lies in their application to Exact Integer Arithmetic.

• The Bareiss Algorithm: This algorithm uses Sylvester’s identity (Bareiss, 1968) to perform Gaussian elimination without introducing fractions. By keeping calculations within the ring of integers, it eliminates rounding errors and minimizes expression swell in symbolic computation.
• Convergence Acceleration: In the theory of Padé approximants, the $ϵ$-algorithm uses these determinantal updates to transform slowly converging sequences into rapidly converging ones. This shares the “spectral tail” logic discussed in on improved Nyström bounds.

🏷️ Application: Exact Linear Solvers

The utility of the Bareiss algorithm extends beyond determinants to the resolution of linear systems $Ax=b$ where $A$ and $b$ have integer or rational entries.

Solving without Precision Loss

1. Fraction-Free Systems: Bareiss uses Sylvester’s Identity to perform divisions that are guaranteed to have no remainder, keeping intermediate coefficients as small as possible.
2. Cramer’s Rule Efficiency: The Bareiss algorithm reduces complexity to $O(n^3)$ by performing fraction-free elimination on the augmented matrix $[A|b]$.
3. Algebraic Robustness: For ill-conditioned systems, the Bareiss approach provides the exact rational solution, avoiding ghost singularities caused by numerical underflow.

📊 Numerical Verification

To demonstrate the practical utility of Sylvester’s Identity, we compare the Bareiss Algorithm (fraction-free elimination) against standard floating-point Gaussian elimination on a scaled Hilbert Matrix (see content/codes/2024 Spring/bareiss_algorithm.py).

Exact Computing vs. Precision Loss

1. The Benchmark: We use a Hilbert matrix ($H_{ij}=\frac{1}{i+j-1}$), which is famously ill-conditioned.

2. The Bareiss Mechanism: The Bareiss algorithm uses the update:

$$A_{ij}^{(k)}=\frac{A_{kk}{A}_{ij}-A_{ik}{A}_{kj}}{A_{k-1,k-1}}$$

where the division is guaranteed to have a zero remainder.

3. The Results:

• Bareiss (Exact): Produces the mathematically true determinant.
• Standard Gauss (Approximate): Uses 64-bit floating point numbers.

🏷️ Notes

• The “condensation” approach inherent in these identities is a precursor to modern discretization methods seen in on convergence of graph Laplacian to manifold’s Laplacian.
• The Schur complement perspective used in the proof is a recurring theme in the stability analysis of on eigenvalue estimate of kernel.

🔗 See Also

• on improved Nyström bounds --- Sylvester’s identity provides the algebraic foundation for the determinantal ratios and recursive updates used in spectral approximation.

📚 References

🐻  Bareiss, E.H. 1968. Sylvester’s identity and multistep integer-preserving gaussian elimination. Mathematics of Computation 22(103), 565–578.

🐻  Sylvester, J.J. 1851. XXXVII. On the relation between the minor determinants of linearly equivalent quadratic functions. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science 1(4), 295–305.