$GL(n)$-dependence of matrices

Basic Information

• Paper ID: 2510.13676
• Title: $GL(n)$-dependence of matrices
• Authors: N. Tsilevich (Braude College of Engineering), Y. Manor (University of Haifa)
• Classification: math.RA (Ring and Algebra)
• Publication Date: October 15, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.13676

Abstract

This paper introduces the concept of $GL(n)$-dependence of matrices, which is a generalization of linear dependence that takes into account the matrix structure. A theorem is subsequently proved that, on one hand, generalizes the fact that any $n+1$ vectors in an $n$-dimensional vector space are linearly dependent, and on the other hand, generalizes the fact that the natural action of the group $GL(n,K)$ on $K^n\setminus\{0\}$ is transitive.

Research Background and Motivation

1. Problem to be Addressed: While the traditional concept of linear dependence applies to matrices (as elements of a linear space), it does not account for the intrinsic structure of matrices. This paper aims to establish a concept of dependence that both maintains the linear algebra framework and fully exploits the matrix structure.
2. Significance of the Problem:
   • Theoretical level: Provides new generalizations of fundamental concepts in linear algebra
   • Applied level: The original motivation stems from theoretical computer science, particularly the KRW conjecture in circuit complexity
3. Limitations of Existing Approaches:
   • Ordinary linear dependence ignores the intrinsic structure of matrices
   • Existing generalizations of dependence (such as algebraic dependence, matroids, etc.) are primarily directed at other mathematical structures
4. Research Motivation: When dealing with a simplified version of the KRW conjecture (semi-monotone circuits), this theoretical tool is needed to prove analogous results for parity query complexity.

Core Contributions

1. Introduction of New Concept: Proposes the definition of $GL(n)$-dependence, replacing scalar multiplication with multiplication by matrices in the general linear group $GL(n,K)$
2. Main Theorem: Proves that any $m+1$ matrices of size $n\times m$ are $GL(n)$-dependent
3. Unified Framework: The theorem simultaneously generalizes two classical results:
   • Any $m+1$ vectors in an $m$-dimensional space are linearly dependent
   • The transitivity of the action of $GL(n)$ on $K^n\setminus\{0\}$
4. Complete Proof: Separately addresses the cases of finite and infinite fields, providing a complete proof

Detailed Methodology

Core Definition

Definition 1 ($GL(n)$-dependence): Matrices $M_1,\ldots,M_k \in M_{n\times m}$ are called $GL(n)$-dependent if there exist $g_1,\ldots,g_{m+1} \in GL(n)\cup\{0\}$ such that:

$\sum_{i=1}^{m+1} g_i M_i = 0, \text{ and not all } g_i \text{ are zero}$

Main Theorem

Theorem 1: Any $m+1$ matrices from $M_{n\times m}$ are $GL(n)$-dependent.

Proof Strategy

Finite Field Case (Relatively Simple)

1. Key Lemma: There exists a linear subspace $H \subset M_{n\times n}$ such that $\dim H = n$ and every nonzero matrix in $H$ is full rank
2. Dimension Argument: Constructs a linear map $f: H^{m+1} \to M_{n\times m}$, and uses $\dim(\text{dom}f) > \dim(\text{img}f)$ to reach the conclusion

Infinite Field Case (More Complex)

Employs double induction:

1. Outer Induction: Induction on $n$
2. Inner Induction: Induction on $m$
3. Base Cases: $n=1$ corresponds to classical linear dependence; $m=1$ corresponds to the transitivity of the $GL(n)$ action
4. Inductive Step: Completes the proof through stepwise correction of "bad indices"

Technical Innovations

1. Structure Preservation: Unlike ordinary linear dependence, $GL(n)$-dependence fully exploits the row space structure of matrices
2. Unified Perspective: Unifies two seemingly unrelated classical results under a single framework
3. Constructive Proof: Particularly in the infinite field case, the "correction" process provides a concrete construction method

Theoretical Analysis

Restatement from Subspace Perspective

Definition 2: Subspaces $L_1,\ldots,L_k \subset K^m$ are called $GL(n)$-dependent if there exist $x_j^{(i)} \in L_i$ such that:

• $\sum_{i=1}^k x_j^{(i)} = 0$ for all $j = 1,\ldots,n$
• $\text{span}\{x_j^{(i)}\}_{j=1}^n$ is either $L_i$ or $\{0\}$, and not all are $\{0\}$

Theorem 3: For each $n \in \mathbb{N}$, any $m+1$ subspaces of $K^m$ with dimension at most $n$ are $GL(n)$-dependent.

Fundamental Properties

1. Dimension Restriction: If subspaces are $GL(n)$-dependent, then each subspace has dimension at most $n$
2. Special Cases: $GL(1)$-dependence is precisely ordinary vector linear dependence
3. Independence: Linearly independent subspaces are $GL(n)$-independent for any $n$
4. Non-equivalence: Linear dependence does not imply $GL(1)$-dependence (except in the one-dimensional subspace case)

Related Work

The paper mentions various generalizations of linear dependence:

1. Algebraic Dependence: A concept in commutative algebra
2. Matroids: Structures in combinatorial mathematics
3. Forking: A concept in model theory
4. Domination: A concept in category theory
5. Weak Dependence and $k$-dependence: Other generalization forms

The contribution of this paper lies in providing a new direction of generalization entirely within the linear algebra framework.

Conclusions and Discussion

Main Conclusions

1. Theoretical Contribution: Successfully establishes a new concept of dependence that accounts for matrix structure
2. Unification: Unifies classical vector linear dependence and group action transitivity under a single theorem
3. Completeness: Provides complete proofs for both finite and infinite fields

Limitations

1. Scope of Application: Primarily a theoretical result with relatively limited practical applications
2. Computational Complexity: The paper does not discuss the algorithmic complexity of determining $GL(n)$-dependence
3. Generalization Potential: Whether further generalization to other groups or structures is possible remains unexplored

Future Directions

1. Computational Aspects: Develop efficient algorithms for determining $GL(n)$-dependence
2. Application Exploration: Seek additional applications beyond circuit complexity
3. Further Generalizations: Consider other groups or more general algebraic structures

In-Depth Evaluation

Strengths

1. Concept Clarity: The definition of $GL(n)$-dependence is natural and easy to understand
2. Rigorous Proof: Separately addresses finite and infinite fields with complete proofs
3. Theoretical Depth: Reveals deep connections between two seemingly unrelated classical results
4. Writing Quality: The paper has clear structure and rigorous logical argumentation

Weaknesses

1. Limited Applications: Beyond the circuit complexity motivation mentioned, lacks other concrete applications
2. Computational Considerations: Does not address related computational problems and algorithms
3. Insufficient Examples: Lacks concrete numerical examples to illustrate the concepts

Impact

1. Theoretical Contribution: Provides new theoretical tools for linear algebra
2. Cross-disciplinary Potential: May find applications in combinatorial mathematics, algebraic geometry, and other fields
3. Reproducibility: The proofs are constructive and theoretically fully reproducible

Applicable Scenarios

1. Theoretical Research: Theoretical problems in linear algebra, group theory, and algebraic geometry
2. Computational Complexity: Circuit complexity and related combinatorial problems
3. Teaching: As an advanced generalization of the linear dependence concept, suitable for graduate-level courses

References

The paper cites 10 important references, covering:

• Commutative algebra textbooks Chambert-Loir, 2021
• Matrix theory Dumas et al., 2010
• Combinatorial theory Feinberg, 1981; Whitney, 1935
• Model theory Shelah, 1990
• Computational complexity Manor & Meir, 2022

These citations demonstrate the interdisciplinary nature and theoretical depth of this work.