拟阵双基间满足独立性的双射映射存在性证明问询

嘿，这个问题我刚好琢磨过！你的二分图思路其实已经踩中了正确方向，咱们把它补全、严谨化就行～

首先先锚定拟阵的核心交换公理：对于拟阵的任意两个基A、B，以及任意元素$a∈A$，必然存在至少一个$b∈B$，使得$(A−{a})∪{b}$仍然是独立集——这是咱们后续推导的关键依据。

接下来把你的二分图思路落地：

• 构造二分图$G$：左部节点是基$A$的所有元素，右部节点是基$B$的所有元素。
• 边的规则：对每个$a∈A$，当且仅当$(A−{a})∪{b}$是独立集时，给$a$和$b$之间连一条边。

现在问题转化为：证明这个二分图存在完美匹配。这里用Hall婚姻定理就刚好合适——只要对左部任意子集$S⊆A$，$S$的邻居集合$N(S)$满足$|N(S)|≥|S|$，就能推出完美匹配存在。

验证Hall条件（反证法） #

假设存在某个$S⊆A$，使得$|N(S)| < |S|$，咱们来推导矛盾：

1. 因为$A$、$B$都是基，所以$|A|=|B|$。那么$B−N(S)$的大小为$|B|−|N(S)| > |B|−|S| = |A|−|S| = |A−S|$。
2. 考虑独立集$A−S$：根据拟阵的扩充性质，独立集的秩等于自身大小，即$rank(cl(A−S))=|A−S|$（$cl$表示闭包）。
3. 对于任意$b∈B−N(S)$，根据边的定义，$b$不能替换$S$中的任何元素，也就是说对所有$a∈S$，$(A−{a})∪{b}$是依赖集，这等价于$b∈cl(A−{a})$。而$A−S⊆A−{a}$，闭包具有单调性，所以$b∈cl(A−S)$。
4. 但$B−N(S)$是大小大于$|A−S|$的独立集，不可能全部包含在秩为$|A−S|$的闭包$cl(A−S)$中——这直接违反了拟阵的秩公理！

因此假设不成立，Hall条件满足，二分图存在完美匹配。这个完美匹配就是咱们要找的双射$\omega:A→B$，每个$a∈A$对应$\omega(a)∈B$，且$(A−{a})∪{\omega(a)}$为独立集。

另外补充一个构造性的思路：可以通过逐步替换来构造双射。从$A$和$B$出发，找$a_1∈A−B$，用交换公理找到$b_1∈B−A$使得$(A−{a_1})∪{b_1}$是基；再用这个新基和$B$重复操作，直到$A$完全转化为$B$，这个替换序列对应的映射就是满足要求的双射。不过二分图+Hall定理的方法更严谨，能直接完成存在性证明。

内容的提问来源于stack exchange，提问作者h94