Maximal generalized rank in graphical matrix spaces

• Published in: Israel journal of mathematics 2023-09, Vol.256 (1), p.297-309
• Main Authors: Guterman, Alexander, Meshulam, Roy, Spiridonov, Igor
• Format: Article
• Language: English
• Subjects: Algebra; Analysis; Applications of Mathematics; Graph theory; Group Theory and Generalizations; Matching; Mathematical and Computational Physics; Mathematics; Mathematics and Statistics; Subspaces; Theorems; Theoretical; Weighting functions
• ISSN: 0021-2172; 1565-8511
• DOI: 10.1007/s11856-023-2508-6

Let M n ( F ) be the space of n × n matrices over a field F . For a subset ℬ ⊂ [ n ] 2 let M ℬ ( F ) = { A ∈ M n ( F ) : A ( i , j ) ∉ ℬ } . Let ν b ( ℬ ) denote the matching number of the n by n bipartite graph determined by ℬ . For S ⊂ M n ( F ) let ρ ( S ) = max{rk( A ): A ∈ S }. Li, Qiao, Wigderson, Wigderson and Zhang [6] have recently proved the following characterization of the maximal dimension of bounded rank subspaces of M ℬ ( F ) . Theorem (Li, Qiao, Wigderson, Wigderson, Zhang): For any ℬ ⊂ [ n ] 2 (1) max { dim W : W ≤ M ℬ ( F ) , ρ ( W ) ≤ k } = max { ∣ ℬ ′ ∣ : ℬ ′ ⊂ ℬ , ν b ( ℬ ′ ) ≤ k } . The main results of this note are two extensions of (1). Let S n denote the symmetric group on [ n ]. For ω : ∐ n = 1 ∞ S n → F ∗ = F \ { 0 } define a function D ω on each M n ( F ) by D ω ( A ) = ∑ σ ∈ S n ω ( σ ) ∏ i = 1 n A ( i , σ ( i ) ) . Let rk ω ( A ) be the maximal k such that there exists a k × k submatrix B of A with D ω ( B )≠0. For S ⊂ M n ( F ) let ρ ω ( S ) = max { rk ω ( A ) : A ∈ S } . The first extension of (1) concerns general weight functions. T heorem : For any ω as above and ℬ ⊂ [ n ] 2 max { dim W : W ≤ M ℬ ( F ) , ρ ω ( W ) ≤ k } = max { ∣ ℬ ′ ∣ : ℬ ′ ⊂ ℬ , ν b ( ℬ ′ ) ≤ k } Let A n ( F ) denote the space of alternating matrices in M n ( F ) . For a graph G ⊂ ( [ n ] 2 ) let A G ( F ) = { A ∈ A n ( F ) : A ( i , j ) = 0 if { i , j } ∉ G } . Let ν ( G ) denote the matching number of G . The second extension of (1) concerns general graphs. T heorem : For any G ⊂ ( [ n ] 2 ) max { dim U : U ≤ A G ( F ) , ρ ( U ) ≤ 2 k } = max { ∣ G ′ ∣ : G ′ ⊂ G , ν ( G ′ ) ≤ k }.