Source author record

K. V. Subrahmanyam

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity math.AC math.RA math.RT Data Structures and Algorithms math.CO math.QA

Catalog footprint

Research overview

4works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Non-commutative Edmonds' problem and matrix semi-invariants

In 1967, Edmonds introduced the problem of computing the rank over the rational function field of an $n\times n$ matrix $T$ with integral homogeneous linear polynomials. In this paper, we consider the non-commutative version of Edmonds' problem: compute the rank of $T$ over the free skew field. It is known that this problem relates to the ring of matrix semi-invariants. In particular, if the nullcone of matrix semi-invariants is defined by elements of degree $\leq σ$ , then there follows a $\mathrm{poly}(n, σ)$ -time randomized algorithm to decide whether the non-commutative rank of $T$ is $<n$ . To our knowledge, previously the best bound for $σ$ was $O(n^2\cdot 4^{n^2})$ over algebraically closed fields of characteristic $0$ (Derksen, 2001). In this article we prove the following results: (1) We observe that by using an algorithm of Gurvits, and assuming the above bound $σ$ for $R(n, m)$ over $\mathbb{Q}$ , deciding whether $T$ has non-commutative rank $<n$ over $\mathbb{Q}$ can be done deterministically in time polynomial in the input size and $σ$ . (2) When $\mathbb{F}$ is large enough, we devise a deterministic algorithm for non-commutative Edmonds' problem in time polynomial in $(n+1)!$ , with the following consequences. (2.a) If the commutative rank and the non-commutative rank of $T$ differ by a constant, then there exists a randomized efficient algorithm that computes the non-commutative rank of $T$ . (2.b) We prove that $σ\leq (n+1)!$ . This not only improves the bound obtained from Derksen's work over algebraically closed field of characteristic $0$ but, more importantly, also provides for the first time an explicit bound on $σ$ for matrix semi-invariants over fields of positive characteristics.

preprint2015arXiv

On generating the ring of matrix semi-invariants

For a field $\mathbb{F}$ , let $R(n, m)$ be the ring of invariant polynomials for the action of $\mathrm{SL}(n, \mathbb{F}) \times \mathrm{SL}(n, \mathbb{F})$ on tuples of matrices -- $(A, C)\in\mathrm{SL}(n, \mathbb{F}) \times \mathrm{SL}(n, \mathbb{F})$ sends $(B_1, \dots, B_m)\in M(n, \mathbb{F})^{\oplus m}$ to $(AB_1C^{-1}, \dots, AB_mC^{-1})$ . In this paper we call $R(n, m)$ the \emph{ring of matrix semi-invariants}. Let $β(R(n, m))$ be the smallest $D$ s.t. matrix semi-invariants of degree $\leq D$ generate $R(n, m)$ . Guided by the Procesi-Razmyslov-Formanek approach of proving a strong degree bound for generating matrix invariants, we exhibit several interesting structural results for the ring of matrix semi-invariants $R(n, m)$ over fields of characteristic $0$ . Using these results, we prove that $β(R(n, m))=Ω(n^{3/2})$ , and $β(R(2, m))\leq 4$ .

preprint2011arXiv

RSK bases and Kazhdan-Lusztig cells

From the combinatorial characterizations of the right, left, and two-sided Kazhdan-Lusztig cells of the symmetric group, 'RSK bases' are constructed for certain quotients by two-sided ideals of the group ring and the Hecke algebra. Applications to invariant theory, over various base rings, of the general linear group and representation theory of the symmetric group are discussed.

preprint2010arXiv

Quantum deformations of the restriction of $GL_{mn}(\C)$-modules to $GL_m(\C) \times GL_n(\C)$

In this paper, we consider the restriction of finite dimensional $GL_{mn} (\C)$-modules to the subgroup ${GL_m (\C)\times GL_n (\C)}$. In particular, for a Weyl module $V_λ (\C^{mn})$ of $U_q(gl_{mn})$ we construct a representation $W_λ$ of $U_q (gl_m)\otimes U_q (gl_n)$ such that at $q=1$ , the restriction of $V_λ (\C^{mn})$ to $U_1 (gl_m)\otimes U_1 (gl_n)$ matches its action on $W_λ$ at $q=1$ . Thus $W_λ$ is a $q$ -deformation of the module $V_λ$ . This is achieved by first constructing a $U_q (gl_m)\otimes U_q (gl_n)$ -module $\wedge^k$ , a $q$ -deformation of the simple $GL_{mn} (\C)$-module $\wedge^k (\C^{mn})$. We also construct the bi-crystal basis for $\wedge^k$ and show that it consists of signed subsets. Next, we develop $U_q (gl_m) \otimes U_q (gl_n)$ -equivariant maps $ψ_{a,b} :\wedge^{a+1} \otimes \wedge^{b-1} \to \wedge^a \otimes \wedge^b$ . This is used as the building block to construct the general $W_λ$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.