論文の概要: Connections between graphs and matrix spaces
- arxiv url: http://arxiv.org/abs/2206.04815v1
- Date: Thu, 9 Jun 2022 23:45:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-10 01:26:10.681105
- Title: Connections between graphs and matrix spaces
- Title（参考訳）: グラフと行列空間の間の接続
- Authors: Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang
- Abstract要約: 特異行列のみを含む$mathcalS_G$の部分空間上の最大の次元は、完全マッチングのない$G$の部分グラフ上の最大サイズに等しいことを示す。
我々は、非巡回性と非公理性、強い接続性と既約性、同型性と共役/合同性の間の接続を確立する。
- 参考スコア（独自算出の注目度）: 11.008438491376555
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given a bipartite graph $G$, the graphical matrix space $\mathcal{S}_G$
consists of matrices whose non-zero entries can only be at those positions
corresponding to edges in $G$. Tutte (J. London Math. Soc., 1947), Edmonds (J.
Res. Nat. Bur. Standards Sect. B, 1967) and Lov\'asz (FCT, 1979) observed
connections between perfect matchings in $G$ and full-rank matrices in
$\mathcal{S}_G$. Dieudonn\'e ({Arch. Math., 1948) proved a tight upper bound on
the dimensions of those matrix spaces containing only singular matrices. The
starting point of this paper is a simultaneous generalization of these two
classical results: we show that the largest dimension over subspaces of
$\mathcal{S}_G$ containing only singular matrices is equal to the maximum size
over subgraphs of $G$ without perfect matchings, based on Meshulam's proof of
Dieudonn\'e's result (Quart. J. Math., 1985).
Starting from this result, we go on to establish more connections between
properties of graphs and matrix spaces. For example, we establish connections
between acyclicity and nilpotency, between strong connectivity and
irreducibility, and between isomorphism and conjugacy/congruence. For each
connection, we study three types of correspondences, namely the basic
correspondence, the inherited correspondence (for subgraphs and subspaces), and
the induced correspondence (for induced subgraphs and restrictions). Some
correspondences lead to intriguing generalizations of classical results, such
as for Dieudonn\'e's result mentioned above, and for a celebrated theorem of
Gerstenhaber regarding the largest dimension of nil matrix spaces (Amer. J.
Math., 1958).
Finally, we show some implications of our results to quantum information and
present open problems in computational complexity motivated by these results.
- Abstract（参考訳）: 双部グラフ $G$ が与えられたとき、グラフィカル行列空間 $\mathcal{S}_G$ は、非零成分が $G$ の辺に対応する位置のみに存在する行列からなる。
Tutte (J. London Math. Soc., 1947), Edmonds (J. Res. Nat. Bur. Standards Sect. B, 1967), Lov\'asz (FCT, 1979) は$G$の完全マッチングと$\mathcal{S}_G$のフルランク行列の間の接続を観察した。
Dieudonn\'e ({Arch. Math., 1948) は、特異行列のみを含むこれらの行列空間の次元の厳密な上界を証明した。
特異行列のみを含む$\mathcal{S}_G$の部分空間上の最大の次元は、ミーシュラムのダイウドン・エの結果の証明(Quart. J. Math., 1985)に基づいて、完全マッチングのない$G$の部分グラフ上の最大サイズに等しいことを示す。
この結果から、グラフの性質と行列空間の間のより多くの接続を確立する。
例えば、非巡回性と非公理性、強い接続性と既約性、同型性と共役性/合同性の間の接続を確立する。
各接続について,基本対応,継承対応(部分グラフと部分空間),誘導対応(誘導部分グラフと制約)の3種類の対応について検討した。
いくつかの対応は、上記のdieudonn\'eの結果や、nil行列空間の最大次元に関するgerstenhaberの有名な定理など、古典的結果の興味深い一般化につながる(amer. j. math., 1958)。
最後に,この結果が量子情報に与える影響を示し,これらの結果に動機づけられた計算複雑性の未解決問題を示す。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - A note on MDS Property of Circulant Matrices [3.069335774032178]
2014年、Gupta と Ray は有限体 $mathbbF_2m$ 上の循環不変行列が最大距離分離(MDS)できないことを証明した。
この記事では、有限体 $mathbbF_2m$ 上のこれらの特性を持つ循環行列について述べる。
論文 参考訳（メタデータ） (2024-06-22T16:00:00Z) - Matrix Compression via Randomized Low Rank and Low Precision
Factorization [47.902465710511485]
現代の行列は数十億の要素を巻き込み、そのストレージと処理は計算資源とメモリ使用量の観点から非常に要求される。
この構造を利用して任意の行列 $mathbfA$ as $mathbfLmathbfR$ の低階分解を求めるアルゴリズムを提案する。
LlaMa-7$bの層を圧縮し,画像圧縮におけるアルゴリズムの有効性を実証的に実証した。
論文 参考訳（メタデータ） (2023-10-17T06:56:57Z) - Multi-Unitary Complex Hadamard Matrices [0.0]
実および複素アダマール行列の集合を追加の対称性制約で解析する。
そのような行列は、量子多体理論、テンソルネットワーク、多部量子絡み合いの分類にいくつかの応用がある。
論文 参考訳（メタデータ） (2023-05-30T20:11:18Z) - Upper bounds for Grothendieck constants, quantum correlation matrices
and CCP functions [0.0]
我々は、有名なグロタンディーク不等式における実かつ複素グロタンディーク定数$K_GmathbbF$のまだ未知の正確な値を求める(1953年以降未解決)。
また、Grothendieck(K_GmathbbR leq sinh(pi/2) approx 2.301$), Krivine(K_GmathbbR leq fracpi2 ln (1 + sqrt2)の有名な上界を復元する。
論文 参考訳（メタデータ） (2023-05-08T02:43:01Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - Non-PSD Matrix Sketching with Applications to Regression and
Optimization [56.730993511802865]
非PSDおよび2乗根行列の次元削減法を提案する。
複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
論文 参考訳（メタデータ） (2021-06-16T04:07:48Z) - Algebraic and geometric structures inside the Birkhoff polytope [0.0]
Birkhoff polytope $mathcalB_d$ は位数 $d$ のすべての双確率行列からなる。
我々は、$mathcalL_d$ と $mathcalF_d$ が平面行列に対して星型であることを証明する。
論文 参考訳（メタデータ） (2021-01-27T09:51:24Z) - Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative
GLASSO and Projection [58.5350491065936]
グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。
最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。
本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-10-25T18:12:50Z) - Compressed sensing of low-rank plus sparse matrices [3.8073142980733]
この写本は、ランクラパース行列と$sスパース行列の和として表現できる$mtimes n$が計算的に抽出可能な方法で復元可能であることを示す同様の保証を開発する。
その結果, 合成問題, 動的地上/静電分離, マルチスペクトルイメージング, ロバストPCAが得られた。
論文 参考訳（メタデータ） (2020-07-18T15:36:11Z) - Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and
Graph Problems [58.83118651518438]
ベクトル行列ベクトルクエリを用いて行列について学習する一般的な問題を考える。
これらのクエリは、固定フィールド上の$boldsymbolumathrmTboldsymbolMboldsymbolv$の値を提供する。
我々は、線形代数、統計、グラフにまたがる様々な問題に対して、新しい上界と下界を提供する。
論文 参考訳（メタデータ） (2020-06-24T19:33:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。