Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn tensor rank and commuting matrices
76
0
0.0
(
0
)
Added by
Pascal Koiran
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Pascal Koiran
Ask ChatGPT about the research
No Arabic abstract
Obtaining superlinear lower bounds on tensor rank is a major open problem in complexity theory. In this paper we propose a generalization of the approach used by Strassen in the proof of his 3n/2 border rank lower bound. Our approach revolves around a problem on commuting matrices: Given matrices Z_1,...,Z_p of size n and an integer r>n, are there commuting matrices Z_1,...,Z_p of size r such that every Z_k is embedded as a submatrix in the top-left corner of Z_k? As one of our main results, we show that this question always has a positive answer for r larger than rank(T)+n, where T denotes the tensor with slices Z_1,..,Z_p. Taking the contrapositive, if one can show for some specific matrices Z_1,...,Z_p and a specific integer r that this question has a negative answer, this yields the lower bound rank(T) > r-n. There is a little bit of slack in the above rank(T)+n bound, but we also provide a number of exact characterizations of tensor rank and symmetric rank, for ordinary and symmetric tensors, over the fields of real and complex numbers. Each of these characterizations points to a corresponding variation on the above approach. In order to explain how Strassens theorem fits within this framework we also provide a self-contained proof of his lower bound.
rate research
Read More
Given three nonnegative integers $p,q,r$ and a finite field $F$, how many Hankel matrices $left( x_{i+j}right) _{0leq ileq p, 0leq jleq q}$ over $F$ have rank $leq r$ ? This question is classical, and the answer ($q^{2r}$ when $rleqminleft{ p,qright} $) has been obtained independently by various authors using different tools (Daykin, Elkies, Garcia Armas, Ghorpade and Ram). In this note, we study a refinement of this result: We show that if we fix the first $k$ of the entries $x_{0},x_{1},ldots,x_{k-1}$ for some $kleq rleqminleft{ p,qright} $, then the number of ways to choose the remaining $p+q-k+1$ entries $x_{k},x_{k+1},ldots,x_{p+q}$ such that the resulting Hankel matrix $left( x_{i+j}right) _{0leq ileq p, 0leq jleq q}$ has rank $leq r$ is $q^{2r-k}$. This is exactly the answer that one would expect if the first $k$ entries had no effect on the rank, but of course the situation is not this simple. The refined result generalizes (and provides an alternative proof of) a result by Anzis, Chen, Gao, Kim, Li and Patrias on evaluations of Jacobi-Trudi determinants over finite fields.
We define the Augmentation property for binary matrices with respect to different rank functions. A matrix $A$ has the Augmentation property for a given rank function, if for any subset of column vectors $x_1,...,x_t$ for for which the rank of $A$ does not increase when augmented separately with each of the vectors $x_i$, $1leq i leq t$, it also holds that the rank does not increase when augmenting $A$ with all vectors $x_1,...,x_t$ simultaneously. This property holds trivially for the usual linear rank over the reals, but as we show, things change significantly when considering the binary and boolean rank of a matrix. We prove a necessary and sufficient condition for this property to hold under the binary and boolean rank of binary matrices. Namely, a matrix has the Augmentation property for these rank functions if and only if it has a unique base that spans all other bases of the matrix with respect to the given rank function. For the binary rank, we also present a concrete characterization of a family of matrices that has the Augmentation property. This characterization is based on the possible types of linear dependencies between rows of $V$, in optimal binary decompositions of the matrix as $A=Ucdot V$. Furthermore, we use the Augmentation property to construct simple families of matrices, for which there is a gap between their real and binary rank and between their real and boolean rank.
Let $G$ be a connected reductive algebraic group over an algebraically closed field $k$, and assume that the characteristic of $k$ is zero or a pretty good prime for $G$. Let $P$ be a parabolic subgroup of $G$ and let $mathfrak p$ be the Lie algebra of $P$. We consider the commuting variety $mathcal C(mathfrak p) = {(X,Y) in mathfrak p times mathfrak p mid [X,Y] = 0}$. Our main theorem gives a necessary and sufficient condition for irreducibility of $mathcal C(mathfrak p)$ in terms of the modality of the adjoint action of $P$ on the nilpotent variety of $mathfrak p$. As a consequence, for the case $P = B$ a Borel subgroup of $G$, we give a classification of when $mathcal C(mathfrak b)$ is irreducible; this builds on a partial classification given by Keeton. Further, in cases where $mathcal C(mathfrak p)$ is irreducible, we consider whether $mathcal C(mathfrak p)$ is a normal variety. In particular, this leads to a classification of when $mathcal C(mathfrak b)$ is normal.
Positive semidefinite rank (PSD-rank) is a relatively new quantity with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix $M$ as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.
This paper studies commuting matrices in max algebra and nonnegative linear algebra. Our starting point is the existence of a common eigenvector, which directly leads to max analogues of some classical results for complex matrices. We also investigate Frobenius normal forms of commuting matrices, particularly when the Perron roots of the components are distinct. For the case of max algebra, we show how the intersection of eigencones of commuting matrices can be described, and we consider connections with Boolean algebra which enables us to prove that two commuting irreducible matrices in max algebra have a common eigennode.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
