Search

A geometric measure for the entanglement of a unit length tensor T ∈ (C n ) ⊗ k is given by − 2 log 2 ⁡ ∥ T ∥ σ , where ∥ ⋅ ∥ σ denotes the spectral norm. A simple induction gives an upper bound of (k − 1) log 2 ⁡ (n) for the entanglement. We show the existence of tensors with entanglement larger than k log 2 ⁡ (n) − log 2 ⁡ (k) − o (log 2 ⁡ (k)). Friedland and Kemp (Proc. AMS, 2018) have similar results in the case of symmetric tensors. Our techniques give improvements in this case. [ABSTRACT FROM AUTHOR]

The following multi-determinantal algebraic variety plays a central role in algebra, algebraic geometry and computational complexity theory: SING n , m {{\rm SING}_{n,m}} , consisting of all m-tuples of n × n {n\times n} complex matrices which span only singular matrices. In particular, an efficient deterministic algorithm testing membership in SING n , m {{\rm SING}_{n,m}} will imply super-polynomial circuit lower bounds, a holy grail of the theory of computation. A sequence of recent works suggests such efficient algorithms for memberships in a general class of algebraic varieties, namely the null cones of linear group actions. Can this be used for the problem above? Our main result is negative: SING n , m {{\rm SING}_{n,m}} is not the null cone of any (reductive) group action! This stands in stark contrast to a non-commutative analog of this variety, and points to an inherent structural difficulty of SING n , m {{\rm SING}_{n,m}}. To prove this result, we identify precisely the group of symmetries of SING n , m {{\rm SING}_{n,m}}. We find this characterization, and the tools we introduce to prove it, of independent interest. Our work significantly generalizes a result of Frobenius for the special case m = 1 {m=1} , and suggests a general method for determining the symmetries of algebraic varieties. [ABSTRACT FROM AUTHOR]

For tensors in , Landsberg provides non-trivial equations for tensors of border rank 2d−3 for d even and 2d−5 for d odd in Landsberg [Non-triviality of equations and explicit tensors in of border rank at least 2m−2. J Pure Appl Algebra. 2015;219(8):3677–3684]. In Derksen and Makam [On non-commutative rank and tensor rank, Linear Multilinear Algebra, published online 2017], we observe that Landsberg's method can be interpreted in the language of tensor blow-ups of matrix spaces, and using concavity of blow-ups, we improve the case for odd d from 2d−5 to 2d−4. The purpose of this paper is to show that the aforementioned results extend to tensors in for any field K. [ABSTRACT FROM AUTHOR]

We study the category of wheeled PROPs using tools from Invariant Theory. A typical example of a wheeled PROP is the mixed tensor algebra V = T (V) ⊗ T (V ⋆) , where T (V) is the tensor algebra on an n -dimensional vector space over a field K of characteristic 0. First we classify all the ideals of the initial object Z in the category of wheeled PROPs. We show that non-degenerate sub-wheeled PROPs of V are exactly subalgebras of the form V G where G is a closed, reductive subgroup of the general linear group GL (V). When V is a finite dimensional Hilbert space, a similar description of invariant tensors for an action of a compact group was given by Schrijver. We also generalize the theorem of Procesi that says that trace rings satisfying the n -th Cayley-Hamilton identity can be embedded in an n × n matrix ring over a commutative algebra R. Namely, we prove that a wheeled PROP can be embedded in R ⊗ V for a commutative K -algebra R if and only if it satisfies certain relations. [ABSTRACT FROM AUTHOR]

We use recent results on matrix semi-invariants to give degree bounds on generators for the ring of semi-invariants for quivers with no oriented cycles. [ABSTRACT FROM AUTHOR]

We study the relationship between the commutative and the non-commutative rank of a linear matrix. We give examples that show that the ratio of the two ranks comes arbitrarily close to 2. Such examples can be used for giving lower bounds for the border rank of a given tensor. Landsberg used such techniques to give non-trivial equations for the tensors of border rank at most in if m is even. He also gave such equations for tensors of border rank at most in if m is odd. Using concavity of tensor blow-ups we show non-trivial equations for tensors of border rank in for odd m for any field of characteristic 0. We also give another proof of the regularity lemma by Ivanyos, Qiao and Subrahmanyam. [ABSTRACT FROM AUTHOR]

It is well known that the ring of polynomial invariants of a reductive group is finitely generated. However, it is difficult to give strong upper bounds on the degrees of the generators, especially over fields of positive characteristic. In this paper, we make use of the theory of good filtrations along with recent results on the null cone to provide polynomial bounds for matrix semi-invariants in arbitrary characteristic, and consequently for matrix invariants. Our results generalize to invariants and semi-invariants of quivers. [ABSTRACT FROM AUTHOR]

We study the left–right action of SL n × SL n on m -tuples of n × n matrices with entries in an infinite field K . We show that invariants of degree n 2 − n define the null cone. Consequently, invariants of degree ≤ n 6 generate the ring of invariants if char ( K ) = 0 . We also prove that for m ≫ 0 , invariants of degree at least n ⌊ n + 1 ⌋ are required to define the null cone. We generalize our results to matrix invariants of m -tuples of p × q matrices, and to rings of semi-invariants for quivers. For the proofs, we use new techniques such as the regularity lemma by Ivanyos, Qiao and Subrahmanyam, and the concavity property of the tensor blow-ups of matrix spaces. We will discuss several applications to algebraic complexity theory, such as a deterministic polynomial time algorithm for non-commutative rational identity testing, and the existence of small division-free formulas for non-commutative polynomials. [ABSTRACT FROM AUTHOR]

We study the ring R ( n , m ) of invariants for the left–right action of SL n × SL n on m -tuples of n × n complex matrices. We show that R ( 3 , m ) is generated by invariants of degree ≤309 for all m . Then, we use a combinatorial description of the invariants to show that R ( n , m ) cannot be generated by invariants of degree < n 2 for large m . We also compute the Hilbert series for several cases. [ABSTRACT FROM AUTHOR]

An $(m,n,a,b)$ -tensor code consists of $m\times n$ matrices whose columns satisfy ‘ $a$ ’ parity checks and rows satisfy ‘ $b$ ’ parity checks (i.e., a tensor code is the tensor product of a column code and row code). Tensor codes are useful in distributed storage because a single erasure can be corrected quickly either by reading its row or column. Maximally Recoverable (MR) Tensor Codes, introduced by Gopalan et al., are tensor codes which can correct every erasure pattern that is information theoretically possible to correct. The main questions about MR Tensor Codes are characterizing which erasure patterns are correctable and obtaining explicit constructions over small fields. In this paper, we study the important special case when $a=1$ , i.e., the columns satisfy a single parity check equation. We introduce the notion of higher order MDS codes ($\mathrm {MDS}(\ell)$ codes) which is an interesting generalization of the well-known MDS codes, where $\ell $ captures the order of genericity of points in a low-dimensional space. We then prove that a tensor code with $a=1$ is MR if the row code is an $\mathrm {MDS}(m)$ code. We then show that $\mathrm {MDS}(m)$ codes satisfy some weak duality. Using this characterization and duality, we prove that $(m,n,a=1,b)$ -MR tensor codes require fields of size $q=\Omega _{m,b}(n^{\min \{b,m\}-1})$. Our lower bound also extends to the setting of $a>1$. We also give a deterministic polynomial time algorithm to check if a given erasure pattern is correctable by the MR tensor code (when $a=1$). [ABSTRACT FROM AUTHOR]

Using the Grosshans Principle, we develop a method for proving lower bounds for the maximal degree of a system of generators of an invariant ring. This method also gives lower bounds for the maximal degree of a set of invariants that define Hilbert's null cone. We consider two actions: The first is the action of SL (V) on S 3 (V) ⊕ 4 , the space of 4-tuples of cubic forms, and the second is the action of SL (V) × SL (W) × SL (Z) on the tensor space (V ⊗ W ⊗ Z) ⊕ 9. In both these cases, we prove an exponential lower degree bound for a system of invariants that generate the invariant ring or that define the null cone. [ABSTRACT FROM AUTHOR]

This paper solves the two-sided version and provides a counterexample to the general version of the 2003 conjecture by Hadwin and Larson. Consider evaluations of linear matrix pencils L = T 0 + x 1 T 1 + ⋯ + x m T m on matrix tuples as L (X 1 , ... , X m) = I ⊗ T 0 + X 1 ⊗ T 1 + ⋯ + X m ⊗ T m. It is shown that ranks of linear matrix pencils constitute a collection of separating invariants for simultaneous similarity of matrix tuples. That is, m -tuples A and B of n × n matrices are simultaneously similar if and only if rk L (A) = rk L (B) for all linear matrix pencils L of size mn. Variants of this property are also established for symplectic, orthogonal, unitary similarity, and for the left-right action of general linear groups. Furthermore, a polynomial time algorithm for orbit equivalence of matrix tuples under the left-right action of special linear groups is deduced. [ABSTRACT FROM AUTHOR]