定理 $n \times n$ 正定値実対称行列 $A,B$ に対して，次の不等式が成り立つ． \[ \det(A+B)^{1/n} \geq \det A^{1/n} + \det B ^{1/n} \]以下の行列式の特徴づけから従う．補題 $n\times n$ 正定値実対称行列 $M $ に対し，次の等式が成り立つ． \[ \inf_{X…

数理最適化 Advent Calendar 2020 20日目の記事です．昨日はyappy0625さんの『天体ショーを整数計画問題で解いてみた。』，明日はshuhei_fさんのSVMの話です．今回紹介するのはBlackwellの接近可能性定理という定理です．一言でいうと，von Neumannのミニマ…

Machine Learning Advent Calendar 2015 1日目の企画です．機械学習・人工知能系の国際会議（ICML, NIPS, AAAIなど）のチュートリアルや論文を眺めたことのある人なら，Submodular Function（劣モジュラ関数）という単語に見覚えがあるかもしれません．実際…

自分のお気に入りの補題のなかにSchwartz-Zippelの補題というものがある．代数，確率，それに組合せ的な話が出てきてとても楽しい補題である．日本語の文献が少ないようなので，ここで紹介しておきたい．補題のStatementは以下の通りである． Schwartz-Zippe…

“quadratic equation”といえば「2次方程式」のことだ．一方で，“quad”といえば「4」を意味する．そもそも“quad”はラテン語の「4」である“quattuor”に由来する．“quad-core processor”はコアが4つあるプロセッサーのことだし，“quarter”は1/4のことだし，“qua…

線形代数の講義で体が主役になることはあまりありません．だいたい R か C くらいを想定しておけば十分です．ところが，有限体上で線形代数を考えると色々と面白いことがあります．そして，組合せ論ではけっこう重要だったりするのです．さて，次の命題のう…

数学協働プログラムシンポジウム『世界は計算！されている』 に行ってきました．数学の一般講演イベントは珍しい気がしますね．全部は書ききれないので，個人的に面白かったところだけ感想を書いていきます． シンポジウムは桜井進さんのオーガナイズで進行…

京大にいた頃に一度だけお会いしたことのある加藤文元先生（現：熊本大教授）の著書ということで，読んでみた．本格的に数学史を扱った本を読んだのは初めてだったので，数学を研究してる者として非常に楽しめた． 数学の「正しさ」とは 本書のテーマは「数…

Vapnik-Chervonekis-Sauer-Shelah Lemmaともいう．いわゆる極値組合せ論の定理．機械学習のVC次元等に応用がある（らしい）．集合 $E$ の部分集合族 $\mathcal{F}$ が集合 $S \subseteq E$ を shutter するとは，任意の $X \subseteq S$ に対して $S \cap F …

面白い問題を見つけたのでメモしておく。 円環状の道路に、ガソリンスタンドが点在している。道路上のすべてのスタンドのガソリンを集めても、ちょうど道路を1周する分のガソリンしかない。今、ガソリンタンクが空っぽの車がある。このとき、あるガソリンス…

型の行列（ただし, A, Dは正方行列*1、A は正則）の行列式と逆行列の公式。 とおき、Schur Complementという。このとき、 であり、 が正則 ⇔ S が正則。S が正則のとき 証明. A の部分は履き出して単位行列にできる。すなわち、 と変形できる（右隅に現れた…

Abel変形ともいう。 という一見ややこしそうな式だが、やってることは簡単で という変形。隣り合う項同士で、余分な項が消えるようになっている。和を差分の和に書き換えたいときに使う。 純粋に代数の公式だが、何故か解析で見ることのほうが多い（気がする…

「2つの封筒問題」という楽しそうな問題を見つけた。 2つの封筒がある。片方の封筒には、もう一方の2倍のお金が入っている（たとえば1万円と2万円など）。プレイヤーはどちらかの片方だけの封筒をもらえる。さらにプレイヤーはどちらか片方の封筒をあけて中…