So we had an assignment in which the following question was asked :
Let $A ∈ Z^{nxn}$ such that each absolute value of an entry is bounded by $U$. Show that the coefficients of the characteristic polynomial of $A$ have binary encoding length polynomial in $log(U)$ and $n$.
and here's the solution :
Without loss of generality we suppose $U ≥ 1$. We denote the coefficient of largest absolute value of the characteristic polynomial of $A$ by $c(U, n)$. Applying Laplace rule to $|A − λI|$ we obtain the recurrence $c(U, n) ≤ U · n · c(U, n − 1)$, which suggests the bound $c(U, n) ≤ n!U^n$ . The latter bound is trivial to prove by induction and it implies that the binary encoding length of $c(U, n)$ is at most $n log(Un)$.
The thing is, I really don't see how different the answer would be if the question was to find an upper bound for the determinant's encoding length. Shouldn't it be different for the characteristic polynomial's coefficients ?
Thank you for your answers.
Ps : for the bravest of you, the following question was about finding a way to compute the characteristic polynomial of a $(n·n)$ matrix by using $n+1$ determinants and the Vandermonde matrix. What would be the complexity ? Could I use Hadamar Bound for a matrix of the form $A-t·I_n$ ? If so How ? I'm not even sure I understood the question that's why I did not post this separately.