6
$\begingroup$

I have heard that it's a well known result (in theoretical computer science?) that if we have a polynomial $p(t_1,\dots,t_n)$ over $\mathbb Q$, we can find matrices $M_0,\dots,M_n/\mathbb Q$ such that $\det(M_0 + M_1t_1 + \dots M_nt_n) = p(t_1,\dots,t_n)$. (What's a reference for this statement?)

In the case of $n = 1$, this is nothing more than the existence of a companion matrix so we might try and prove the result inductively. Namely, we think of $p(t_1,\dots,t_n)$ as a one variable polynomial over $\mathbb Q[t_2,\dots,t_n]$ and find matrices $P_0,P_1$ denied over this ring such that $\det(P_0 + P_1t_1) = p(t)$.

Now, if there were some "quasi-determinant" operator that let us write a matrix $A(t)$ as the quasi determinant of some other matrix $Q_0 + Q_1t$ and this quasi-determinant satisfied a nice recursivity (I believe it's called hereditary in Gelfond's work?), we could make the above inductive strategy go through. Is there such an operator?

To be very explicit, the question is the following:

Given a matrix $A(t)$ where the entries are polynomials in $\mathbb Q[t]$, can we find matrices/operators $Q_0,Q_1$ and a nice"quasi-determinant" such that $\mathrm{qdet}(Q_0 + Q_1t) = A(t)$.

An alternative (generalized) way to phrase the question is that we are given a polynomial $p(t)$ over a non-commutative ring and we want to find a description of it as the quasi-determinant of $P_0+P_1t$ for some $P_0,P_1.$

Improve this question
$\endgroup$
7
  • $\begingroup$ Are there any restrictions on the sizes of the matrices $M_j$? $\endgroup$
    – David E Speyer
    Commented Mar 4, 2021 at 16:50
  • $\begingroup$ I don't particulary care about the sizes but I heard that the result proves an exponential blowup on the sizes (wrt n). $\endgroup$
    – Asvin
    Commented Mar 4, 2021 at 16:51
  • 3
    $\begingroup$ This paper seems to contain the desired algorithm arxiv.org/ftp/arxiv/papers/1804/1804.00145.pdf $\endgroup$
    – Vlad Matei
    Commented Mar 4, 2021 at 18:01
  • $\begingroup$ @VladMatei Thank you! I am still interested in the broader question of finding an appropriate quasi-determinant, however. $\endgroup$
    – Asvin
    Commented Mar 4, 2021 at 18:22
  • 1
    $\begingroup$ Maybe a smaller but more definite question to start with is to characterize which matrices of polynomials can be realized as adjugates of matrices with linear entries, or matrix of $k$-minors ($k$-wedge) of a matrix with linear entries. Of course the size is $\binom{m}{k}\times\binom{n}{k}$, the entries have degree $k$, and the determinant of an adjugate is a pure power, but surely there are more conditions. $\endgroup$
    – Zach Teitler
    Commented Mar 4, 2021 at 19:35

0

Reset to default

You must log in to answer this question.