7
$\begingroup$

I'm working on some questions in tropical geometry, and my problem led me to create the following generalization of a determinant:

Let $A$ be an $m \times n$ matrix with $m \le n$, and positive integer multiplicities $m_i$ assigned to the rows with $\sum_{i=1}^m m_i =n$ so $A$ is "square with multiplicity". I consider labeled partitions $\mathcal I= \{I_1, \dots, I_m\}$ of $\{1, \dots, n\}$ with $|I_i| = m_i$. Then the "determinant with multiplicity" is $$ \sum_{\mathcal I} \operatorname{sgn}(\mathcal I)\prod_{i=1}^m \prod_{k\in I_i} A_{ik}. $$ Notice that when $m=n$ (so all $m_i=1$) then this is just the usual determinant.

I actually haven't thought about what $\operatorname{sgn}(\mathcal I)$ should be in general, because I created that definition by lifting from a tropical definition-- I call a matrix "tropically non-singular with multiplicity" if $$ \max_{\mathcal I} \left\{\sum_{i} \sum_{k \in I_i} A_{ik}\right\}, $$ is achieved exactly once.

I expect "tropically non-singular with multiplicity" to have some nice properties generalizing those of the usual (Strumfels) tropical non-singularity. Some of those proofs use a lift to Puiseaux series and then the properties of the usual determinant, so if I want to imitate those proofs, I would need to understand the properties of the "determinant with multiplicity".

So my question is: does anybody recognize the definitions above as something that has been studied before? If so, can you point me to a reference?

EDIT

Some more motivation: As a function, the second display above is the same as the tropical determinant/permanent of the actual square matrix formed by repeating the $i$th row $m_i$ times. I prefer my version because it eliminates repeated terms that "come only from" the repeated rows, that is, a matrix with a repeated row is not automatically considered to be singular. I guess this is funny classically, but I think I have a tropical geometric interpretation that makes sense.

$\endgroup$
  • 1
    $\begingroup$ A good notion of the sign probably does not exist. The $\mathcal I$ are counted by multinomial coefficients, and there is no good way to assign sign to these sets or partition them into two. For instance, the multinomial coefficient is sometimes odd. How do you assign signs then? $\endgroup$ – Will Sawin Jan 7 '14 at 21:22
  • $\begingroup$ I think the true question is what kind of properties you expect. To much extent, the determinant is the only function with "nice" properties, and square matrices are the only format where such functions exist. Certainly, this is a vague statement; for details, try to dig in the direction of hyperdeterminants. $\endgroup$ – Alex Degtyarev Jan 7 '14 at 22:17
  • $\begingroup$ Have you looked at the coefficient of $t^{n-m}$ in the characteristic polynomial of the obvious square matrix? $\endgroup$ – Allen Knutson Jan 7 '14 at 22:37
8
$\begingroup$

Summary

There is a clear connection to the permanent, which, if I understand correctly, yields the same tropicalization, and a more speculative connection to the determinant. The reason is that OP's formula can be rewritten as an immanant-like expression evaluated on an auxiliary matrix $\widehat{A}$ obtained by repeating the rows of $A$ according to the multiplicities $m_i.$ For arguably the most natural choice of the coefficients in the expansion, where they are all equal $1$, one obtains the permanent of $\widehat{A}$ (up to a constant multiple). On the other hand, one can also choose the coefficients for an arbitrary $m\leq n$ in a way that reproduces the determinant when $m=n.$ I don't know whether this leads to a meaningful generalization of the determinant.


Analysis

Modulo the choice of the coefficients, the procedure outlined in the question amounts to the following.

  1. Replace the rectangular $m\times n$ matrix $A$ with the square $n\times n$ matrix $\widehat{A}$ by repeating the $i$th row of $A$ $m_i$ times.

  2. Consider the row expansion of the "immanant" $\sum_{\sigma\in S_n}k_{\sigma}\prod_{i=1}^n \widehat{A}_{i,\sigma(i)},$ where $k_\sigma$ are some coefficients that need to be specified ("the signs").

The partition $\mathcal{I}=\{I_1,I_2,\ldots,I_m\}$ of the set $\{1,2,\ldots,n\}$ of the column indices from the original formula is $\large\{\sigma$(first $m_1$ indices), $\sigma$(next $m_2$ indices), $\ldots$, $\sigma$(last $m_m$ indices)$\large\}$ and the coefficient $\operatorname{sgn}(\mathcal{I})=\sum k_\sigma,$ with the sum taken over all permutations $\sigma$ corresponding to that partition $\mathcal{I}.$

In the case that $k_\sigma=1$ for all $\sigma\in S_n,$ we get the permanent of $\widehat{A},$ which is equal to the constant $(\prod_{i=1}^{m}m_i!)$ times (OP's expression for all coefficients equal to $1$). Although this is non-standard in the context of permanents, the constant can be eliminated by setting $k_{\sigma}=0$ for permutations $\sigma$ that "scramble" some of the parts $I_k$, cf the next paragraph.

One can also consider the following "determinant" choice of $k_\sigma.$ It is defined to be $\operatorname{sgn}(\sigma)$ if the descent set of $\sigma$ is contained in $\{m_1,m_1+m_2,\ldots,m_1+\ldots+m_{m-1}\}$ and $0$ otherwise. In other words, for each partition $\mathcal{I}$ consider the element $\sigma_{\mathcal{I}}\in S_n$ which maps the first $m_1$ indices to $I_1$ preserving the order, the next $m_2$ indices to $I_2$ preserving the order, and so on, and set $\operatorname{sgn}(\mathcal{I})=\operatorname{sgn}(\sigma_{\mathcal{I}}).$ The resulting expression is always non-trivial and for $m=n,$ it yields $\det(A).$ On the other hand, if $m<n$ then the matrix $\widehat{A}$ contains repeating rows and hence its determinant is $0.$


Examples.

  1. For $m=1$, the matrix $A$ is a single row, $A=[a_1,a_2,\ldots,a_n],$ the multiplicity $m_1=n,$ there is only one possible partition, where $I_1=\{1,2,\ldots,n\},$ and (assuming the coefficient is $1$) the OP's expression is $\prod_{i=1}^n a_i,$ that is the product of the entries of $A.$ The matrix $\widehat{A}$ is the row $[a_1,a_2,\ldots,a_n]$ repeated $n$ times and its permanent is $n!$ times the product of the entries of $A.$ Even though the "determinant" choice of the "sign" coefficient is $1,$ it appears more natural to view the product of the entries of $A$ as an analogue of the permanent rather than the determinant. On the other hand, unless $n=1,$ the determinant of $\widehat{A}$ is $0$ (corresponding to the "sign" coefficient being $0$).

  2. For $m=2,$ the matrix $A$ has two rows and $n$ columns and the multiplicity is a pair $(p,q)$ of natural numbers that add up to $n.$ A partition $\mathcal{I}=\{I,J\}$ of the set of column indices with $|I|=p$ and $|J|=q$ leads to the choice of $p$ entries in the first row of $A$ and $q$ entries in the second row in such a way that every column contains exactly one chosen entry. OP's procedure is to multiply the chosen entries together and take a linear combination of these products over different choices with to-be-specified coefficients $\operatorname{sgn}(I,J).$ It is easy to see that this is effectively the same as repeating the first row of $A$ $p$ times and the second row $q$ times to form a square matrix $\widehat{A}$ and computing its "immanant" as above. There are two natural choices for the coefficients: $\operatorname{sgn}(I,J)=1$, leading to the permanent of $\widehat{A},$ and $\operatorname{sgn}(I,J)=\operatorname{sgn}(\sigma),$ where $\sigma$ is the shortest permutation corresponding to the partition $(I,J)$, namely $\sigma(i)=I_i$ for $1\leq i\leq p$ and $\sigma(p+i)=J_{i}$ for $1\leq i\leq q$ (it is assumed that the parts $I$ and $J$ are represented by increasing sequences of indices).

  3. For $m=n,$ the multiplicities are necessarily all equal to $1$ and partition $\mathcal{I}$ is the same as a permutation $\sigma$ of $\{1,2,\ldots,n\}.$ In this case, the recipe amounts to the usual row expansion of the "immanant" of $A$, which gives the determinant or the permanent if the coefficients $k_\sigma$ are $\operatorname{sgn}\sigma$ or $1,$ respectively. Of course, there are also other possibilities, for example, $k_{\sigma}=\chi_{\lambda}(\sigma),$ where $\chi_{\lambda}$ is an irreducible character of the symmetric group $S_n,$ corresponds to the immanant $\operatorname{Imm}_{\lambda}(A)$ of $A.$

$\endgroup$
  • $\begingroup$ Thank you for your response-- I had not seen immanants before. Indeed my original motivation is from repeated rows-- I edited my question to include that. $\endgroup$ – Drew Jan 8 '14 at 16:04
  • $\begingroup$ You are welcome, Drew! Without enough background knowledge, I can't be sure, but here are 2 things to keep in mind re your original motivation. Firstly, it's just possible that the appropriate de-tropicalization of the "determinant with multiplicities" is not the usual determinant - for example, it may be an immanant-like expression where the coefficients are not prescribed in advance (they may be generic variables). And secondly, not everything generalizes and it may sometimes be necessary to work out completely new proofs in your context rather than trying to imitate existing ones. $\endgroup$ – Victor Protsak Jan 9 '14 at 5:46
  • $\begingroup$ Also, a less philosophical comment regarding the $m\times n$ matrix $A$ versus a square matrix $\widehat{A}$ with repeated rows. The determinant is exceptional in that its value on a matrix with repeating rows vanishes. Thus a determinant minor vanishes if the row indices repeat. However, this is not so for the permanent and similar expressions. In particular, it's perfectly fine classically to talk about a permanent minor of order $n$ of an $m\times n$ matrix, where the row indices include some repetitions (or multiplicities). $\endgroup$ – Victor Protsak Jan 9 '14 at 5:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.