---
OA_place: repository
OA_type: green
_id: '22188'
abstract:
- lang: eng
  text: "A fundamental fact about bounded-degree graph expanders is that three notions
    of expansion—vertex expansion, edge expansion, and spectral expansion—are all
    equivalent. In this paper, we study to what extent such a statement is true for
    linear-algebraic notions of expansion.\r\n\r\nThere are two well-studied notions
    of linear-algebraic expansion, namely, dimension expansion (defined in analogy
    to vertex expansion of graphs) and quantum expansion (defined in analogy to spectral
    expansion of graphs). Lubotzky and Zelmanov proved that the latter implies the
    former. We prove that the converse is false: There are dimension expanders which
    are not quantum expanders. This also answers in the negative questions of Lubotzky--Zelmanov
    and Dvir--Shpilka on the relation between dimension expansion and Kazhdan's property
    T.\r\n\r\nMoreover, this asymmetry is explained by the fact that there are two
    distinct linear-algebraic analogues of edge expansion of graphs. The first of
    these is quantum edge expansion, which was introduced by Hastings, and which he
    proved to be equivalent to quantum expansion. We introduce a new notion, termed
    dimension edge expansion, which we prove is equivalent to dimension expansion
    and which is implied by quantum edge expansion. Thus, the separation above is
    implied by a finer one: dimension edge expansion is strictly weaker than quantum
    edge expansion. This new notion also leads to a new, more modular proof of the
    Lubotzky--Zelmanov result that quantum expanders are dimension expanders."
article_number: '1'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Yinan
  full_name: Li, Yinan
  last_name: Li
- first_name: Youming
  full_name: Qiao, Youming
  last_name: Qiao
- first_name: Avi
  full_name: Wigderson, Avi
  last_name: Wigderson
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
- first_name: Chuanqi
  full_name: Zhang, Chuanqi
  last_name: Zhang
citation:
  ama: Li Y, Qiao Y, Wigderson A, Wigderson Y, Zhang C. On linear-algebraic notions
    of expansion. <i>Theory of Computing</i>. 2025;21. doi:<a href="https://doi.org/10.4086/toc.2025.v021a001">10.4086/toc.2025.v021a001</a>
  apa: Li, Y., Qiao, Y., Wigderson, A., Wigderson, Y., &#38; Zhang, C. (2025). On
    linear-algebraic notions of expansion. <i>Theory of Computing</i>. Theory of Computing
    Exchange. <a href="https://doi.org/10.4086/toc.2025.v021a001">https://doi.org/10.4086/toc.2025.v021a001</a>
  chicago: Li, Yinan, Youming Qiao, Avi Wigderson, Yuval Wigderson, and Chuanqi Zhang.
    “On Linear-Algebraic Notions of Expansion.” <i>Theory of Computing</i>. Theory
    of Computing Exchange, 2025. <a href="https://doi.org/10.4086/toc.2025.v021a001">https://doi.org/10.4086/toc.2025.v021a001</a>.
  ieee: Y. Li, Y. Qiao, A. Wigderson, Y. Wigderson, and C. Zhang, “On linear-algebraic
    notions of expansion,” <i>Theory of Computing</i>, vol. 21. Theory of Computing
    Exchange, 2025.
  ista: Li Y, Qiao Y, Wigderson A, Wigderson Y, Zhang C. 2025. On linear-algebraic
    notions of expansion. Theory of Computing. 21, 1.
  mla: Li, Yinan, et al. “On Linear-Algebraic Notions of Expansion.” <i>Theory of
    Computing</i>, vol. 21, 1, Theory of Computing Exchange, 2025, doi:<a href="https://doi.org/10.4086/toc.2025.v021a001">10.4086/toc.2025.v021a001</a>.
  short: Y. Li, Y. Qiao, A. Wigderson, Y. Wigderson, C. Zhang, Theory of Computing
    21 (2025).
date_created: 2026-06-29T12:14:06Z
date_published: 2025-04-12T00:00:00Z
date_updated: 2026-07-14T09:47:56Z
day: '12'
doi: 10.4086/toc.2025.v021a001
extern: '1'
external_id:
  arxiv:
  - '2212.13154'
fulldoi: https://doi.org/10.4086/toc.2025.v021a001
intvolume: '        21'
keyword:
- linear algebraic expansion
- quantum expanders
- dimension expanders
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2212.13154
mathsc:
- 05C18
- 68R10
month: '04'
oa: 1
oa_version: Preprint
publication: Theory of Computing
publication_identifier:
  issn:
  - 1557-2862
publication_status: published
publisher: Theory of Computing Exchange
quality_controlled: '1'
scopus_import: '1'
status: public
title: On linear-algebraic notions of expansion
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 21
year: '2025'
...