Metraipolis › archive › dc_2b9faade896f

On computing the determinant over a ring — arXiv:2611.07786

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.07786
License (as archived): CC0-1.0
Archived: 2026-11-06T14:54:33.578Z
SHA-256 of the archived text: 586e464f92268b291153eb4b65f115a78b71f5f63b36f6da59fb555ac76fd344
Stable URL of this page: https://metraipolis.com/documento/dc_2b9faade896f

How to cite

On computing the determinant over a ring — arXiv:2611.07786 — arXiv (en), https://arxiv.org/abs/2611.07786 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2b9faade896f (Metraipolis archive dc_2b9faade896f, sha256 586e464f92268b291153eb4b65f115a78b71f5f63b36f6da59fb555ac76fd344)

BibTeX

@misc{dc2b9faade896f,
  title = {On computing the determinant over a ring — arXiv:2611.07786},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.07786},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2b9faade896f; sha256 586e464f92268b291153eb4b65f115a78b71f5f63b36f6da59fb555ac76fd344},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.07786. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

An algorithm is presented for computing the determinant and the characteristic polynomial of a matrix $A$ over an arbitrary commutative ring R. The algorithm uses $O(n^\omega)$ ring additions, subtractions and multiplications, where $\omega>2$ is a feasible exponent for matrix multiplication, that is, such that two $n\times n$ matrices over R can be multiplied using $O(n^{\omega})$ ring operations. The algorithm involves no division and no zero test, and its control depends only on $n$: for each $n$ it is a straight-line program. The approach combines a polynomial matrix point of view and a block Krylov point of view on the characteristic polynomial, which makes Strassen's elimination of divisions efficient. A bivariate matrix $\lambda I-L(t)$, obtained from $A$ by a homotopy, is compressed in $\log n$ steps, each of which halves the dimension while only doubling the degree in $\lambda$. The cost of the homotopy is controlled by truncating the power series in $t$ at an order that only grows with the compression steps, from a constant to $n$.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Symbolic Computation (cs.SC) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2611.07786 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-06T14:27:27.634Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).