Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

On the Minimal Polynomial of a Matrix

Thanh Minh HoangContact Information and Thomas ThieraufContact Information

(6)  Abt. Theoretische Informatik, Universität Ulm, 89069 Ulm, Germany
Abstract
We investigate the complexity of the degree and the constant term of the minimal polynomial of a matrix. We show that the degree of the minimal polynomial behaves as the matrix rank.
We compare the constant term of the minimal polynomial with the constant term of the characteristic polynomial. The latter is known to be computable in the logspace counting class GapL. We show that this holds also for the minimal polynomial if and only if the logspace exact counting class C=L is closed under complement. The latter condition is one of the main open problems in this area.
As an application of our techniques we show that the problem to decide whether a matrix is diagonalizable is complete for AC 0(C=L), the AC 0-closure of C=L.
This work was supported by the Deutsche Forschungsgemeinschaft

Contact Information Thanh Minh Hoang
Email: hoang@informatik.uni-ulm.de

Contact Information Thomas Thierauf
Email: thierauf@informatik.uni-ulm.de
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.106 • Server: mpweb21
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)