English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

For standard algorithms verifying positive definiteness of a matrix$A\in\mathbb{M}_n(\mathbb{R})$ based on Sylvester's criterion, thecomputationally pessimistic case is this when $A$ is positive definite. Wepresent two algorithms realizing the same task for$A\in\mathbb{M}_n(\mathbb{Z})$, for which the case when $A$ is positivedefinite is the optimistic one. The algorithms have pessimistic computationalcomplexities $\mathcal{O}(n^3)$ and $\mathcal{O}(n^4)$ and they rely onperforming certain edge transformations, called inflations, on theedge-bipartite graph (=bigraph) $\Delta=\Delta(A)$ associated with $A$. Weprovide few variants of the algorithms, including Las Vegas type randomizedones with precisely described maximal number of steps. The algorithms work verywell in practice, in many cases with a better speed than the standard tests.Moreover, the algorithms yield some additional information on the properties onthe quadratic form $q_A:\mathbb{Z}^n\to\mathbb{Z}$ associated with a matrix$A$. On the other hand, our results provide an interesting example of anapplication of symbolic computing methods originally developed for differentpurposes, with a big potential for further generalizations in matrix problems.  This is an extended version of the article [A. Mr\'oz, Effectivenondeterministic positive definiteness test for unidiagonal integral matrices,Proceedings SYNASC 2016, IEEE Computer Society CPS (2016), 65-71] in which wediscussed the algorithm of the complexity $\mathcal{O}(n^4)$.

Two nondeterministic positive definiteness tests for unidiagonal integral matrices