  For standard algorithms verifying positive definiteness of a matrix
$A\in\mathbb{M}_n(\mathbb{R})$ based on Sylvester's criterion, the
computationally pessimistic case is this when $A$ is positive definite. We
present two algorithms realizing the same task for
$A\in\mathbb{M}_n(\mathbb{Z})$, for which the case when $A$ is positive
definite is the optimistic one. The algorithms have pessimistic computational
complexities $\mathcal{O}(n^3)$ and $\mathcal{O}(n^4)$ and they rely on
performing certain edge transformations, called inflations, on the
edge-bipartite graph (=bigraph) $\Delta=\Delta(A)$ associated with $A$. We
provide few variants of the algorithms, including Las Vegas type randomized
ones with precisely described maximal number of steps. The algorithms work very
well in practice, in many cases with a better speed than the standard tests.
Moreover, the algorithms yield some additional information on the properties on
the 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 an
application of symbolic computing methods originally developed for different
purposes, with a big potential for further generalizations in matrix problems.
  This is an extended version of the article [A. Mr\'oz, Effective
nondeterministic positive definiteness test for unidiagonal integral matrices,
Proceedings SYNASC 2016, IEEE Computer Society CPS (2016), 65-71] in which we
discussed the algorithm of the complexity $\mathcal{O}(n^4)$.
