Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Compound Determinant Identity for Rectangular Matrices
175
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A compound determinant identity for minors of rectangular matrices is established. As an application, we derive Vandermonde type determinant formulae for classical group characters.
rate research
Read More
One approach to make progress on the symbolic determinant identity testing (SDIT) problem is to study the structure of singular matrix spaces. After settling the non-commutative rank problem (Garg-Gurvits-Oliveira-Wigderson, Found. Comput. Math. 2020; Ivanyos-Qiao-Subrahmanyam, Comput. Complex. 2018), a natural next step is to understand singular matrix spaces whose non-commutative rank is full. At present, examples of such matrix spaces are mostly sporadic, so it is desirable to discover them in a more systematic way. In this paper, we make a step towards this direction, by studying the family of matrix spaces that are closed under the commutator operation, that is matrix Lie algebras. On the one hand, we demonstrate that matrix Lie algebras over the complex number field give rise to singular matrix spaces with full non-commutative ranks. On the other hand, we show that SDIT of such spaces can be decided in deterministic polynomial time. Moreover, we give a characterization for the matrix Lie algebras to yield a matrix space possessing singularity certificates as studied by Lovasz (B. Braz. Math. Soc., 1989) and Raz and Wigderson (Building Bridges II, 2019).
Let $mathbb{F}_q$ be an arbitrary finite field of order $q$. In this article, we study $det S$ for certain types of subsets $S$ in the ring $M_2(mathbb F_q)$ of $2times 2$ matrices with entries in $mathbb F_q$. For $iin mathbb{F}_q$, let $D_i$ be the subset of $M_2(mathbb F_q)$ defined by $ D_i := {xin M_2(mathbb F_q): det(x)=i}.$ Then our results can be stated as follows. First of all, we show that when $E$ and $F$ are subsets of $D_i$ and $D_j$ for some $i, jin mathbb{F}_q^*$, respectively, we have $$det(E+F)=mathbb F_q,$$ whenever $|E||F|ge {15}^2q^4$, and then provide a concrete construction to show that our result is sharp. Next, as an application of the first result, we investigate a distribution of the determinants generated by the sum set $(Ecap D_i) + (Fcap D_j),$ when $E, F$ are subsets of the product type, i.e., $U_1times U_2subseteq mathbb F_q^2times mathbb F_q^2$ under the identification $ M_2(mathbb F_q)=mathbb F_q^2times mathbb F_q^2$. Lastly, as an extended version of the first result, we prove that if $E$ is a set in $D_i$ for $i e 0$ and $k$ is large enough, then we have [det(2kE):=det(underbrace{E + dots + E}_{2k~terms})supseteq mathbb{F}_q^*,] whenever the size of $E$ is close to $q^{frac{3}{2}}$. Moreover, we show that, in general, the threshold $q^{frac{3}{2}}$ is best possible. Our main method is based on the discrete Fourier analysis.
The determinants of ${pm 1}$-matrices are calculated by via the oriented hypergraphic Laplacian and summing over an incidence generalization of vertex cycle-covers. These cycle-covers are signed and partitioned into families based on their hyperedge containment. Every non-edge-monic family is shown to contribute a net value of $0$ to the Laplacian, while each edge-monic family is shown to sum to the absolute value of the determinant of the original incidence matrix. Simple symmetries are identified as well as their relationship to Hadamards maximum determinant problem. Finally, the entries of the incidence matrix are reclaimed using only the signs of an adjacency-minimal set of cycle-covers from an edge-monic family.
We prove a weighted generalization of the formula for the number of plane vertex-labeled trees.
We introduce a variant of PCPs, that we refer to as rectangular PCPs, wherein proofs are thought of as square matrices, and the random coins used by the verifier can be partitioned into two disjoint sets, one determining the row of each query and the other determining the column. We construct PCPs that are efficient, short, smooth and (almost-)rectangular. As a key application, we show that proofs for hard languages in $NTIME(2^n)$, when viewed as matrices, are rigid infinitely often. This strengthens and simplifies a recent result of Alman and Chen [FOCS, 2019] constructing explicit rigid matrices in FNP. Namely, we prove the following theorem: - There is a constant $delta in (0,1)$ such that there is an FNP-machine that, for infinitely many $N$, on input $1^N$ outputs $N times N$ matrices with entries in $mathbb{F}_2$ that are $delta N^2$-far (in Hamming distance) from matrices of rank at most $2^{log N/Omega(log log N)}$. Our construction of rectangular PCPs starts with an analysis of how randomness yields queries in the Reed--Muller-based outer PCP of Ben-Sasson, Goldreich, Harsha, Sudan and Vadhan [SICOMP, 2006; CCC, 2005]. We then show how to preserve rectangularity under PCP composition and a smoothness-inducing transformation. This warrants refined and stronger notions of rectangularity, which we prove for the outer PCP and its transforms.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
