'Run the Berkowitz algorithm and return a vector whose entries
are the coefficients of the characteristic polynomial of `self`.
Given N x N matrix, efficiently compute
coefficients of characteristic polynomials of \'self\'
without division in the ground domain.
This method is particularly useful for computing determinant,
principal minors and characteristic polynomial when \'self\'
has complicated coefficients e.g. polynomials. Semi-direct
usage of this algorithm is also important in computing
efficiently sub-resultant PRS.
Assuming that M is a square matrix of dimension N x N and
I is N x N identity matrix, then the Berkowitz vector is
an N x 1 vector whose entries are coefficients of the
polynomial
charpoly(M) = det(t*I - M)
As a consequence, all polynomials generated by Berkowitz
algorithm are monic.
For more information on the implemented algorithm refer to:
[1] S.J. Berkowitz, On computing the determinant in small
parallel time using a small number of processors, ACM,
Information Processing Letters 18, 1984, pp. 147-150
[2] M. Keber, Division-Free computation of sub-resultants
using Bezout matrices, Tech. Report MPI-I-2006-1-006,
Saarbrucken, 2006'

def _eval_berkowitz_vector(self):

    if ((self.rows == 0) and (self.cols == 0)):
        return self._new(1, 1, [S.One])
    elif ((self.rows == 1) and (self.cols == 1)):
        return self._new(2, 1, [S.One, (- self[(0, 0)])])
    (submat, toeplitz) = self._eval_berkowitz_toeplitz_matrix()
    return (toeplitz * submat._eval_berkowitz_vector())
