精华内容
下载资源
问答
  • 群和对称
    千次阅读
    2020-07-06 20:22:16

    群和对称性

    啥是群啊

    群是一组操作的集合,满足如下性质:

    1. 集合中必须包含一个操作 e e e,代表不做任何操作
    2. 如果集合中包含一个操作 a a a,那么就必须包含另一个操作 a − 1 a^{-1} a1,使得先后进行这两个操作的效果等于 e e e
    3. 如果集合中包含两个操作 a a a b b b,那么先进行操作 a a a再进行操作 b b b(记作 b a ba ba)对应的操作也必须在此集合中; a b ab ab同理。
    4. 如果集合中包含三个操作 a a a b b b c c c,那么 ( a b ) c (ab)c (ab)c两个操作的效果必须等价于 a ( b c ) a(bc) a(bc)两个操作,记作 a b c abc abc

    但搞数学的人不爱这么说,按他们的说法群(Group)就是一个满足如下要求的集合 G G G

    1. 封闭性 a b ∈ G , ∀ a , b ∈ G ab \in G, \forall a, b \in G abG,a,bG
    2. (Catalan律) ( a b ) c = a ( b c ) , ∀ a , b , c ∈ G (ab)c = a(bc), \forall a, b, c \in G (ab)c=a(bc),a,b,cG
    3. ∃ e ∈ G , 使 得 e a = a , ∀ a ∈ G \exist e \in G, 使得ea = a, \forall a \in G eG,使ea=a,aG
    4. ∃ a − 1 ∈ G , 使 得 a − 1 a = e , ∀ a ∈ G \exist a^{-1} \in G, 使得a^{-1}a = e, \forall a \in G a1G,使a1a=e,aG

    给定一个操作 a a a,上面说了它的逆操作 a − 1 a^{-1} a1必须存在,实际上 a − 1 a^{-1} a1也必须是唯一的。换句话说,不可能同时存在两个不同的操作 a − 1 a^{-1} a1 a ′ − 1 a'^{-1} a1,使得 a a − 1 = a a ′ − 1 = e aa^{-1} = aa'^{-1} = e aa1=aa1=e。你能看出来这是为什么吗?

    这和对称性有啥关系

    对称性是事物在某种操作下保持不变的特性。见过摊煎饼吧?摊主把煎饼翻个面,煎饼还是这张煎饼。再翻一次,你会说,那跟没翻一样。这里翻个面就是一种操作 a a a,再翻一次就跟没翻一样(我承认煎饼更熟了),意思就是 a a = e aa = e aa=e。是不是惊奇的发现摊煎饼这个例子中 a a a的逆操作 a − 1 a^{-1} a1就是它自己? a = a − 1 a = a^{-1} a=a1

    然后你会发现,在这个例子中,重要的不是事物,重要的是操作。不管你是摊煎饼,还是翻牌,还是翻什么其他的东西。上面这个性质都成立。群这个概念把所有这些保持事物不变的操作提取了出来,因为他们是对称性的核心。

    进一步的讨论

    上面举的例子中只包含两个操作,翻面和什么都不做(看着煎饼糊掉)。在数学家研究的例子中,群中包含的操作通常会多得多,甚至可能包含无限多个操作。比如说,摊煎饼的时候,摊主通常还会转一转,据说这样受热更均匀。我们假设摊主每次都会把煎饼顺时针转90°吧。那么转180°,270°也就必须加入到群里。还漏了什么吗?也许你会说,还有它们的逆操作。你领悟地倒是挺快,不过逆时针转90°就相当于转270°,逆时针转180°就相当于转180°,逆时针转270°就相当于转90°。转360°相当于什么都没做(除了受热更均匀了),它们都已经在群里了。但是,如果翻个面然后再转呢?是的,还有三个,翻个面转90°,翻个面转180°和翻个面转270°也得在这个群里。

    加上这些操作之后,我们得到了一个更大的群。那么原来那个只有两个操作的群就叫做这个更大的群的子群。你也应该注意到,单看这些旋转操作的话,连同什么都不做的这个操作,它们也形成一个子群。把复杂的大群拆分成简单的子群来研究是数学家们惯用的技俩。请读者思考,翻面转的那三个操作连同什么都不做构成另一个子群吗?

    嗯,不构成,因为如果只考虑那四个操作的话,它们的组合操作不在其中。但是它们似乎就是一伙的啊,你会说。
    是的,它们有另一个名字,叫做子群的陪集。具体地说,任取一个子群,再任取一个操作与子群中的操作一一组合,所形成的这个新的集合就叫做原来那个子群的陪集。两个相异的陪集的交集一定为空,全体陪集的并集为原来的群(想想为什么)。因此我们说,陪集构成了群的一个划分

    陪集分为两种,形如 a H aH aH这样的(其中 a a a是群里的元素, H H H是子群),叫左陪集;类似地,像 H a Ha Ha这样的,就叫右陪集。一般来说,左陪集和右陪集并不相等。不过如果它们竟然相等了(也就是说对于任意的 a a a,有 a H = H a aH = Ha aH=Ha),那么就值得专门研究。数学家觉得这样的子群很正规(并不是),于是就给他们取名叫正规子群

    a H = H a aH = Ha aH=Ha,注意啊,这个条件这么要求很有意思。在群中也有这么一个操作 e e e,满足 a e = e a ae = ea ae=ea啊。这样看来,这个正规子群就很像是 e e e的角色。实际上,对于正规子群,它的全体陪集的集合会形成一个新的群,它自己就是这个群中的 e e e。这个新的群,就叫做原来的群对它的这个正规子群的商群。记作 G H G \over H HG。读者可以思考如下两个问题:

    1. 为什么要求这个子群一定是正规子群?非正规子群能形成商群吗?为什么。
    2. 为什么这个新的群取名叫商群?(提示,数一数 G G G H H H以及 G H G \over H HG中元素的个数。)

    扯得有点远了。让我们再回到摊煎饼这个例子。不知道你是否还有别的发现?反正我是注意到一个很明显的事实,那就是群里所有这些操作并不是同等重要的。其中一些操作可以由其他操作组合而成。具体来说,只要我们有翻面这个动作,执行两次,就有了什么都不做这个动作。我们有转90°这个动作,执行两次,三次,四次,就有了其他的旋转动作。你也可以验证,群中的所有操作都可以由翻面和转90°这两个操作组合而成。这两个操作叫做这个群的生成元

    更多相关内容
  • 层次结构遵循[Wang等人,2003年]中定义对称层次结构。 2011]。 对称层次结构用于训练在我们的论文“ PartNet:用于细粒度和层次形状分割的递归零件分解网络”中提出的PartNet模型。 通常,PartNet-Symh可用于基于...
  • 首先, 定义犹豫模糊相对熵、对称交互熵, 并基于信息论的角度提出一个新的犹豫模糊相似度公式; 然后, 利用相似度公式构造相似系数矩阵, 基于编网聚类方法对犹豫模糊进行聚类; 最后, 通过算例验证了所提出方法的...
  • 针对带“*”值的不完备决策系统,提出一种基于非对称选择相似关系的扩充粗糙模型,通过定义“选择相似”的概念来合理地控制未知值和已知值的相似程度,克服了“*”值可与任意值相似的不足。理论分析表明,该模型...
  • 首先给出了标识映射对称性的定义,并指出,二进制标识映射的对称性是BICM(-ID)系统的固有特性,该对称性同构于m阶超立方的对称群。然后基于BICM(-ID)的对称性,提出一种改进的二进制交换算法(IBSA)。该算法的搜索空间为...
  • 在本文中,我们研究了由Σ8(X,n + k +1)类的X半对称联合定义的二元关系的完整半群的生成,并找到了给定半群的唯一不可约生成
  • 在本文中,我们研究了由Σ2(X,4)类的X半对称定义的完整半群的生成
  • 基于模糊理论, 设计对称局部二值模式算子, 获取稳健特征; 定义数据投影降维机制与量化规则, 生成紧凑的中间Hash比特序列; 构造一维组合混沌映射, 建立加密模型, 完成比特序列扩散, 以生成图像Hash; 并引入汉明...
  • rorschach:对称绘画应用

    2021-06-16 10:30:42
    为此,我创建了自己的库 jen.js,其中包括一个绘画功能(用于创建笔画)和一个镜像功能(用于在创建者定义对称线上反映元素)。 请使用我的库来创建您自己的应用程序! 用户可以自定义笔画开始大小、结束大小,...
  • 在请求生成算法的基础上,引入了转移应答消息和请求重构消息,重新定义应答消息的结构以使其能够携带更多的信息,重新设计了分布式互斥算法的相关过程,从而改进了Makawa类分布式互斥算法的性能。该算法具有较高...
  • 是群,a∈G,a的整数次幂可归纳定义为: a0 = e an+1 = an· a, n∈N a-n = (a-1)n, n∈N 容易证明,∀m,n∈I,am··an = am+n, (am)n = amn. 定义:设<G,·>是群,a∈G,若∀n∈I+,an≠ e,则称a的阶是...

    元素的阶

    设<G,·>是群,a∈G,a的整数次幂可归纳定义为:

    1. a0 = e
    2. an+1 = an· a, n∈N
    3. a-n = (a-1)n, n∈N

    容易证明,∀m,n∈I,am··an = am+n, (am)n = amn.

    定义:设<G,·>是群,a∈G,若∀n∈I+,an ≠ e,则称a的阶是无限的;否则称使得an = e的最小整数n为a的阶,此时a的阶也称为a的周期,常用|a|表示

    • 在群<I,+>中,∀i∈I - {0},i的阶都是无限的
    • 在群<N4,+4>中,|0| = 1|,|1| = 4,|2| = 2,|3| = 4

    定理:设<G,·>是群,a∈G,且|a| = n,k∈I,则$|a^k| = \frac{n}{(k,n)}$.特别地,|a-1| = |a|

     

    循环群

    循环群:在群(G,·)中,若存在a∈G,使得G = {an | n∈G},则称(G,·)为循环群。

    • (Z,+)是一个无限阶循环群,生成元是1和-1
    • <Nm,+m>是m阶循环群,生成元是1

    循环群的结构相当简单,我们完全可以刻画出全部循环群的同构类

    定理:设群G = (a),则循环群只有两种。若|a|无限,则G≌<I,+>;若|a|=n∈I+,则 G≌<Nn,+n>

    由本定理有,同阶的循环群必同构,因此把n阶循环群记作Cn

    推论:设G是n阶有限群,a∈G,则G = (a)当且仅当|a| = n。

    就是上面定理的推论,此推论说明循环群生成元的阶与群的阶是相同的

     

    定理:设群G=(a)

    • 若G是无限群,则G只有两个生成元a和a-1
    • 若|G| = n∈I+,则G=(ar)当且仅当(r,n) = 1,即生成元有φ(n)个,其中φ(n)为欧拉函数

    证:

    (1)必要性:已知a是生成元,因为a = (a-1)-1,所以a-1也是生成元。充分性:设am∈G是生成元,即G = (am),因为a∈G,所以∃t∈I,使得a = (am)t,所以amt-1=e.因为G是无限群,mt-1=0,故m=t=1或m=t=-1,故只有两个生成元a和a-1.

    (2)必要性:设G=(ar),由前面的推论知|ar| = n,由前面关于元素的阶的定理得$|a^r| = \frac{n}{(r,n)}$,故(r,n) = 1。充分性:设(r,n) = 1,则∃s,t∈I使得rs + nt = 1,于是$a = a^{rs+nt} = {(a^r)}^s·{(a^n)}^t$,因为|a| = n,an = e,所以a = (ar)s,故G = (ar).

    例如:设G为12阶循环群{e,a,a2,...,a11},因为与12互质的12以内的数有1,5,7,11,所以G有4个生成元,分别是a,a5,a7,a11.

     

    定理:设群G=(a),|G|=n,则对于n的每个正因子d,有且仅有一个d阶子群,因此,n阶循环群的子群的个数恰为n的正因子的个数.

    例如:12阶循环群有6个子群,分别是(a),(a2),(a3),(a4),(a6),(a12).

     

    变换群

    我们知道,给定一个集合A,<AA,°>是亚群,其中°是函数合成运算,令PA为A到A的所有双射的集合,则<PA,°>是群,其中1A是单位元,每个f∈PA的逆元是其逆函数f-1.

    变换群:设A为集合,群<PA,°>的子群称为A的变换群

    Cayley定理:任意一个群都与某个变换群同构。证明略

     

    置换群是特殊的变换群,在代数中有重要地位

     

    对称群和置换群

    对称群:设S是非空有限集,Sn是S的所有置换的集合(n是集合的基数),°是函数的复合运算,则<Sn,°>是一个群,称作n次对称群。易知|Sn| = n!

    置换群:对称群的子群称为置换群,含有n个元素的子群称为n次置换群

    作为Cayley定理的直接推论,我们有

    推论:任意一个有限群都与某个置换群同构

     

    置换还有第二种表示方法,为此需要引入循环的概念

    定义:把S中的元素i1变成i2,i2变成i3,... ik又变成i1,并使S中的其余元素保持不变的置换称为循环,也称轮换,记(i1 i2  ... ik),k称为循环长度。特别的,长度为2的循环称为对换.

    注意,同一循环的表示并不唯一。长度为1的循环是恒等置换。

    例如:$$\bigl(\begin{smallmatrix}
    1 \, 2 \, 3 \, 4 \, 5 & \\
    4 \, 2 \, 5 \, 3 \, 1 &
    \end{smallmatrix}\bigr)$$

    定理:

    • 任意置换都可表示成若干无公共元素的循环之积
    • 任意置换都可表示成若干个对称之积,且对换个数的奇偶性不变

     

    陪集

    定义:设H是群G的子群,a∈G.

    1. 集合a·H = {a·h | h∈H} 称为H关于a的左陪集
    2. 集合H·a = {h·a | h∈H} 称为H关于a的右陪集

    定理:设H是群G的子群,在G上定义二元关系R为:对任意a,b∈G,(a,b)∈R当且仅当b-1a∈H,则R是G上的等价关系,且其对应的等价类与左陪集相同,为R(a) = a·H。类似的,在G上定义二元关系R为:对任意a,b∈G,(a,b)∈R当且仅当ab-1∈H,则R是G上的等价关系,且其对应的等价类与右陪集相同,为R(a) = H·a。

    证:(1)先证明R是等价关系,自反性:∀a∈G,因为a-1 · a = e∈H,所以aRa。对称性::∀a,b∈G,若aRb,b-1 · a∈H,由于H是群,一个元素的逆元也在群中,所以(b-1 · a)-1∈H,所以bRa。传递性:∀a,b,c∈G,若aRb和bRc,即b-1 · a∈H,c-1 · b∈H,H是群,则满足封闭性,所以c-1 · a = (c-1 · b) · (b-1 · a) ∈H,即aRc。

    (2)再证明R(a) = aH,对∀x∈R(a),有aRx,由对称性知xRa,即a-1x∈H,因此存在h∈H,使得a-1x = h,即x=ah∈aH,得到R(a)⊆aH;反过来,假设x∈aH,则存在h∈H,使得x=ah,即a-1x=h,所以xRa,得到aH⊆R(a);综上的,R(a) = aH

    定理:H是G的有限子群,∀a∈H,|aH| = |Ha| = |H|.

    该定理说明同一子群的左陪集和右陪集的基数相等,且等于子群的基数

    定理:所有左陪集的个数等于所有右陪集的个数

    证:只需给出SL和SR之间的双射即可。

    该定理是指陪集本身的个数,上一个定理是指陪集中元素的个数,是不同的

     

    定义:设H是群G的子群,H在G中所有左(右)陪集的个数称为H在G中的指数,记作[G,H]

     

    拉格朗日定理

    Lagrange定理:设H设有限群G的子群,则|H|整除|G|,且|G| = |H| * [G:H]

    推论一:有限群G的每个元素的阶均能整除G的阶

    证:∀a∈G,(a)≤G,所以|(a)|整除|G|,即|a|整除|G|

    推论二:质数阶的群必为循环群

    证:设G是p阶群,其中p是质数,由(1),∀a∈G,|a|整除p,若a≠e,则|a| ≠ 1,所以|a| = p,故G = (a).

     

    正规子群与商群

    正规子群:设H是G的子群,若∀a∈G,aH = Ha,则称H是G的正规子群,或正则子群、不变子群,记作H◁G

    在正规子群中左陪集和右陪集相等,因此统称为陪集

    例如:

    • Abel群的子群都是正规子群
    • 任意群都有两个平凡正规子群,即{e}和它本身

    定理:设H ≤ G,H◁G当且仅当∀a∈G,aHa-1⊆H

    该定理可用来判定是否为正规子群

    定理:设H ≤ G,则G关于H的陪集关系R是G上的同余关系

    证:前面已经证明过R是等价关系,下面证明R关于·满足置换性质.

    ∀a,b,c,d∈G,若aRb,cRd,则aH = Hb,cH = Hd,所以(ac)H = a(cH) = a(Hd) = (aH)d = (Hb)d = H(bd).故(ac)R(bd)。

    注:

    • 群的任意子群的左(右)陪集关系不一定是群上的同余关系,但是正规子群的陪集关系一定是
    • 正规子群可诱导出同余关系,反之,同余关系也可以诱导出正规子群

     

    商群:设(H,·)是(G,·)的一个正规子群,定义G/H为{Ha |a∈G},对任意的Ha,Hb∈G/H,定义G/H上的运算°为Ha ° Hb = Hab,(补充完整是(H·a) ° (H·b) = H·a·b),则(G/H,°)构成一个群,称为G关于H的商群

    证:证明其是一个群,良性的、封闭性、结合性、有单位元、有逆元。略。

    例如:

     

     

    参考链接:中国大学mooc 刘铎 离散数学

    转载于:https://www.cnblogs.com/lfri/p/10083976.html

    展开全文
  • 定义对称拟向量均衡问题的近似解序列,以此分别给出了对称拟向量均衡问题的适定性和唯一适定性概念。证明在一定条件下,对称拟向量均衡问题的适定性等价于ε→0时,ε-近似解与解间的Hausdorff距离的极限为零。唯一...
  • 对称:对象的骨架(对称)图。 1:骨架; 0:无骨架。 SK-LARGE中的图片展示 骨骼秤 骨架点的比例尺定义为其到最近边缘点的距离,可以通过Matlab函数``bwdist''轻松实现。 附加了一个Matlab脚本augmentation.m ,...
  • 分析变分不等式问题的经典方法之一是通过间隙函数的概念将其转化为等效的优化问题。... 在定值对称和局部α-Holder假设下,在描述一个值向量拟变分不等式问题的解空间域的值图上获得了误差界限结果。
  • 定义了直觉模糊关系的截以及并给出了它们的基本性质,同时分别讨论了自反、对称、传递直觉模糊关系与经典二元关系之间的等价刻画;其次,提出直觉模糊关系的定义域与值域的概念;最后,分析了直觉模糊关系合成的截...
  • 其次引入了一种松弛归一化条件的模糊鉴别分析算法,根据每一个样本的隶属度对散布矩阵重定义所做的贡献,将它融入到特征抽取的过程中,从而得到完整有效的模糊特征向量,解决了传统LDA方法中的最终特征维数受类别数...
  • 我们表明,通过适当的扩展,即使在存在超多重子的情况下,该对偶也可以推广到阿贝尔量表的情况。 通过定义沿着标量流的弗洛伊登塔尔对偶性,可以证明由弗洛伊登塔尔算子链接的电荷和计量的两种配置在黑洞视界共享...
  • 基于对称传递关系,定义粗糙近似,由此建立拓扑及内部、闭包;针对构建拓扑,确立基与邻域基,得到第二可数性、第一可数性、可分性、林德洛夫性等可数性特征;提供实例分析。研究结果基于新二元关系揭示粗糙与...
  • 本文主要针对线性代数中的正定矩阵、实对称矩阵、矩阵特征值分解以及矩阵 SVD 分解进行总结。 如果你对这篇文章可感兴趣,可以点击「【访客必读 - 指引页】一文囊括主页内所有高质量博客」,查看完整博客分类与对应...

    前言

    本文主要针对线性代数中的正定矩阵、实对称矩阵、矩阵特征值分解以及矩阵 SVD 分解进行总结。

    如果你对这篇文章可感兴趣,可以点击「【访客必读 - 指引页】一文囊括主页内所有高质量博客」,查看完整博客分类与对应链接。


    正定矩阵

    1. 概念

    首先正定矩阵是定义在对称矩阵的基础上,其次对于任意非零向量 x \textbf{x} x,若 x T A x > 0 \textbf{x}^T\textbf{\textit{A}}\textbf{x}>0 xTAx>0 恒成立,则矩阵 A \textbf{\textit{A}} A 为正定矩阵;若 x T A x ≥ 0 \textbf{x}^T\textbf{\textit{A}}\textbf{x}\geq 0 xTAx0 恒成立,则矩阵 A \textbf{\textit{A}} A 为半正定矩阵。

    2. 物理意义

    任意非零向量 x \textbf{x} x 经过矩阵 A A A 线性变换后,与原先向量的夹角 ≤ 90 \leq 90 90 度。

    3. 其他充要条件

    • 充要条件1: 矩阵 A \textbf{\textit{A}} A 的全部特征值都是正数
      • 推论: A \textbf{\textit{A}} A 正定,则 ∣ A ∣ > 0 |\textbf{\textit{A}}|>0 A>0,即 A \textbf{\textit{A}} A 可逆(有时会根据矩阵正定来判断是否可逆)
      • 推论: A \textbf{\textit{A}} A 正定,则 A \textbf{\textit{A}} A 与单位阵合同,即存在可逆阵 C \textbf{\textit{C}} C,使得 C T AC = E \textbf{\textit{C}}^T\textbf{\textit{A}}\textbf{\textit{C}}=\textbf{\textit{E}} CTAC=E 成立
    • 充要条件2: 矩阵 A \textbf{\textit{A}} A 的各阶顺序主子式都是正数,即 Δ i > 0 \Delta_i>0 Δi>0
      • 其中 Δ i \Delta_i Δi 表示矩阵 A \textbf{\textit{A}} A i i i 行与前 i i i 列组成的子矩阵的行列式的值
      • 推论: ∣ A ∣ > 0 |A|>0 A>0 A A A 一定可逆

    实对称矩阵

    1. 概念

    矩阵为方阵,其中元素均为实数,且 A = A T \textbf{\textit{A}}=\textbf{\textit{A}}^T A=AT

    2. 性质

    • 性质1: 实对称矩阵的特征值都是实数。
      • 假设 λ \lambda λ x \textbf{x} x 分别为矩阵 A \textbf{\textit{A}} A 的特征值、特征向量,即 A x = λ x \textbf{\textit{A}}\textbf{x}=\lambda \textbf{x} Ax=λx
      • 等式两边取共轭,即 a + b i ‾ = a − b i \overline{a+bi}=a-bi a+bi=abi A ‾ x ‾ = λ ‾ x ‾ \overline{\textbf{\textit{A}}}\overline{\textbf{x}}=\overline{\lambda} \overline{\textbf{x}} Ax=λx A \textbf{\textit{A}} A 是实对称矩阵,因此 A = A T = A ‾ \textbf{\textit{A}}=\textbf{\textit{A}}^T=\overline{\textbf{\textit{A}}} A=AT=A,即 A x ‾ = λ ‾ x ‾ \textbf{\textit{A}}\overline{\textbf{x}}=\overline{\lambda} \overline{\textbf{x}} Ax=λx
      • 等式两边取转置,则 x T A = λ x T \textbf{x}^T\textbf{\textit{A}}=\lambda \textbf{x}^T xTA=λxT
      • x T A x ‾ = λ ‾ x T x ‾ = λ x T x ‾ \textbf{x}^T\textbf{\textit{A}}\overline{x}=\overline{\lambda}\textbf{x}^T\overline{\textbf{x}}=\lambda \textbf{x}^T\overline{\textbf{x}} xTAx=λxTx=λxTx
      • ( λ − λ ‾ ) ∥ x ∥ 2 2 = 0 (\lambda-\overline{\lambda})\left\|\textbf{x}\right\|_2^2=0 (λλ)x22=0,由于 ∥ x ∥ 2 2 > 0 \left\|\textbf{x}\right\|_2^2>0 x22>0,因此 λ = λ ‾ \lambda=\overline{\lambda} λ=λ λ \lambda λ 为实数
    • 性质2: 实对称矩阵不同特征值所对应的特征向量必定正交。
      • 假设 A x 1 = λ 1 x 1 \textbf{\textit{A}}\textbf{x}_1=\lambda_1 \textbf{x}_1 Ax1=λ1x1 A x 2 = λ 2 x 2 \textbf{\textit{A}}\textbf{x}_2=\lambda_2 \textbf{x}_2 Ax2=λ2x2 成立
      • x 1 T A = λ 1 x 1 T \textbf{x}_1^T\textbf{\textit{A}}=\lambda_1 \textbf{x}_1^T x1TA=λ1x1T
      • x 1 T A x 2 = λ 1 x 1 T x 2 = λ 2 x 1 T x 2 \textbf{x}_1^T\textbf{\textit{A}}\textbf{x}_2=\lambda_1 \textbf{x}_1^T\textbf{x}_2=\lambda_2\textbf{x}_1^T\textbf{x}_2 x1TAx2=λ1x1Tx2=λ2x1Tx2
      • ( λ 1 − λ 2 ) x 1 T x 2 = 0 (\lambda_1-\lambda_2)\textbf{x}_1^T\textbf{x}_2=0 (λ1λ2)x1Tx2=0,因此 x 1 \textbf{x}_1 x1 x 2 \textbf{x}_2 x2 正交
    • 性质3: 实对称矩阵相同特征值所对应的特征向量必定线性无关。
      • 证明较繁琐,不详细展开
      • 线性无关的向量可以通过施密特正交化转为正交向量
        • 对于线性无关向量组 x 1 , x 2 , . . . , x n \textbf{x}_1,\textbf{x}_2,...,\textbf{x}_n x1,x2,...,xn,转为正交向量组 y 1 , y 2 , . . . , y n \textbf{y}_1,\textbf{y}_2,...,\textbf{y}_n y1,y2,...,yn
        • y 1 = x 1 \textbf{y}_1=\textbf{x}_1 y1=x1
        • y i = x i − ∑ j = 1 i − 1 x i T y j y j T y j y j \textbf{y}_i=\textbf{x}_i-\sum\limits_{j=1}^{i-1}\displaystyle\frac{\textbf{x}_i^T\textbf{y}_j}{\textbf{y}_j^T\textbf{y}_j}\textbf{y}_j yi=xij=1i1yjTyjxiTyjyj
      • 由于新的正交向量都是原来线性无关向量的线性组合,而原先的线性无关向量对应的特征值均相同,因此新的正交向量也均为该相同特征值对应的特征向量
    • 性质4: 任何一个实对称矩阵,都可以正交对角化。
      • 正交对角化,即存在一个正交矩阵 Q ( Q T = Q − 1 ) \textbf{\textit{Q}}(\textbf{\textit{Q}}^T=\textbf{\textit{Q}}^{-1}) Q(QT=Q1) 使得 Q T AQ = D \textbf{\textit{Q}}^T\textbf{\textit{A}}\textbf{\textit{Q}}=\textbf{\textit{D}} QTAQ=D,其中 D \textbf{\textit{D}} D 是一个对角矩阵
      • 实对称矩阵,一定有 n n n 个解,因为实对称矩阵特征值都是实数,因此一共有 n n n 个实特征值(包括重特征值)—— 性质 1 1 1
      • 不同特征值对应的特征向量正交,相同特征值也一定存在对应的正交向量 —— 性质 2 , 3 2,3 2,3
      • 实对称矩阵,一定有 n n n 个正交特征向量,因此可以特征值分解,即该性质成立
    • 性质5: 实对称矩阵的非零特征值个数等于矩阵的秩
      • 矩阵 A \textbf{\textit{A}} A 相似于对角矩阵, P − 1 AP = D \textbf{\textit{P}}^{-1}\textbf{\textit{A}}\textbf{\textit{P}}=\textbf{\textit{D}} P1AP=D
      • 对角矩阵 D \textbf{\textit{D}} D 的秩 = 矩阵 A \textbf{\textit{A}} A 的秩 = D \textbf{\textit{D}} D 非零特征值个数
      • 矩阵 A \textbf{\textit{A}} A 与 矩阵 D \textbf{\textit{D}} D 相似,则特征值相同
    • 性质6:实对称矩阵不一定可逆,但若可逆,则一定是实对称矩阵
      • 0 矩阵对称不可逆
      • ( A − 1 ) T = ( A T ) − 1 = A − 1 (A^{-1})^T=(A^T)^{-1}=A^{-1} (A1)T=(AT)1=A1

    矩阵特征值分解

    1. 概念

    n ∗ n n*n nn 的方阵 A \textbf{\textit{A}} A,由 A x = λ x \textbf{\textit{A}}\textbf{x}=\lambda \textbf{x} Ax=λx 可以得到 AV = V Λ \textbf{\textit{A}}\textbf{\textit{V}}=\textbf{\textit{V}}\Lambda AV=VΛ

    • 如果方阵 A \textbf{\textit{A}} A n n n 个线性无关的特征向量,则 V \textbf{\textit{V}} V 可逆
    • A = V Λ V − 1 \textbf{\textit{A}}=\textbf{\textit{V}}\Lambda\textbf{\textit{V}}^{-1} A=VΛV1
    • 其中矩阵 V \textbf{\textit{V}} V 的列为方阵 A \textbf{\textit{A}} A 的特征向量, Λ = d i a g ( λ 1 , λ 2 , . . . , λ n ) , λ i ≥ λ i + 1 \Lambda=diag(\lambda_1,\lambda_2,...,\lambda_n),\lambda_i\geq \lambda_{i+1} Λ=diag(λ1,λ2,...,λn),λiλi+1

    矩阵 SVD 分解

    1. 概念

    任意一个矩阵 A \textbf{\textit{A}} A 都可以分解为 A = U Σ V T \textbf{\textit{A}}=\textbf{\textit{U}}\Sigma\textbf{\textit{V}}^T A=UΣVT,其中 U , V \textbf{\textit{U}},\textbf{\textit{V}} U,V 均为正交单位矩阵, Σ \Sigma Σ 为对角矩阵。

    2. 证明

    • A T A = ( U Σ V T ) T U Σ V T = V Σ 2 V T \textbf{\textit{A}}^T\textbf{\textit{A}}=(\textbf{\textit{U}}\Sigma\textbf{\textit{V}}^T)^T\textbf{\textit{U}}\Sigma\textbf{\textit{V}}^T=\textbf{\textit{V}}\Sigma^2\textbf{\textit{V}}^T ATA=(UΣVT)TUΣVT=VΣ2VT,由于 A T A \textbf{\textit{A}}^T\textbf{\textit{A}} ATA 为实对称矩阵,因此 V \textbf{\textit{V}} V 为矩阵 A T A \textbf{\textit{A}}^T\textbf{\textit{A}} ATA 对应特征向量组成的正交单位阵。
    • A A T = U Σ V T ( U Σ V T ) T = U Σ 2 U T \textbf{\textit{A}}\textbf{\textit{A}}^T=\textbf{\textit{U}}\Sigma\textbf{\textit{V}}^T(\textbf{\textit{U}}\Sigma\textbf{\textit{V}}^T)^T=\textbf{\textit{U}}\Sigma^2\textbf{\textit{U}}^T AAT=UΣVT(UΣVT)T=UΣ2UT,由于 A A T \textbf{\textit{A}}\textbf{\textit{A}}^T AAT 为实对称矩阵,因此 U \textbf{\textit{U}} U 矩阵 A A T \textbf{\textit{A}}\textbf{\textit{A}}^T AAT 对应特征向量组成的正交单位阵。
    • AV = U Σ \textbf{\textit{A}}\textbf{\textit{V}}=\textbf{\textit{U}}\Sigma AV=UΣ,其中 Σ \Sigma Σ 为对角阵,因此 A v i = σ i u i \textbf{\textit{A}}\textbf{v}_i=\sigma_i\textbf{u}_i Avi=σiui,由此可以得到对角矩阵 Σ \Sigma Σ,其中 σ i \sigma_i σi 就是奇异值。
    • A m ∗ n = U m ∗ m Σ m ∗ n V n ∗ n T \textbf{\textit{A}}_{m*n}=\textbf{\textit{U}}_{m*m}\Sigma_{m*n}\textbf{\textit{V}}_{n*n}^T Amn=UmmΣmnVnnT

    3. 几何角度

    矩阵 U , V U,V U,V 仅负责旋转, Σ \Sigma Σ 负责放缩,具体示意图如下:
    在这里插入图片描述

    4. SVD 压缩

    如下所示,仅选取前 r r r 个不为零的奇异值,可以实现无损压缩。注意非零奇异值的个数等于矩阵 A A A 的秩。

    在这里插入图片描述

    5. 计算伪逆

    在这里插入图片描述

    6. Eckart-Young Theorem

    如果矩阵 B \mathbf{B} B 的秩为 k k k,则 ∣ ∣ A − B ∣ ∣ ≥ ∣ ∣ A − A k ∣ ∣ ||A-B||\geq||A-A_k|| ABAAk 对如下三个矩阵范数成立:

    • ∣ ∣ A ∣ ∣ 2 = σ 1 ||A||_2=\sigma_1 A2=σ1,即最大的奇异值
    • ∣ ∣ A ∣ ∣ N u c l e a r = ∑ i = 1 r σ i ||A||_{Nuclear}=\sum\limits_{i=1}^r\sigma_i ANuclear=i=1rσi
    • Frobenius norm = ∣ ∣ A ∣ ∣ 2 , 1 = ∣ ∣ A ∣ ∣ F = ( t r ( A T A ) ) 1 / 2 = ( ∑ i = 1 m ∑ j = 1 n a i j 2 ) 1 / 2 =||A||_{2,1}=||A||_F=(tr(A^TA))^{1/2}=(\sum\limits_{i=1}^m\sum\limits_{j=1}^na_{ij}^2)^{1/2} =A2,1=AF=(tr(ATA))1/2=(i=1mj=1naij2)1/2

    其中 A \mathbf{A} A A k \mathbf{A_k} Ak 定义如下:
    A = U Σ V T = ∑ i = 1 r σ i u i v i T A k = U k Σ k V k T = ∑ i = 1 k σ i u i v i T \begin{aligned} & \mathbf{A}=\mathbf{U}\Sigma\mathbf{V}^T=\sum\limits_{i=1}^r \sigma_i\mathbf{u}_i\mathbf{v}_i^T\\ & \mathbf{A}_k=\mathbf{U}_k\Sigma_k\mathbf{V}_k^T=\sum\limits_{i=1}^k \sigma_i\mathbf{u}_i\mathbf{v}_i^T \end{aligned} A=UΣVT=i=1rσiuiviTAk=UkΣkVkT=i=1kσiuiviT

    需要注意,矩阵乘上一个正交矩阵,其奇异值不会发生变化,即上述涉及的矩阵范数不会改变。

    7. LSI

    计算不同 q u e r y query query 之间的相似程度,常用于推荐系统。
    在这里插入图片描述
    更多 SVD 的应用:

    展开全文
  • 密码学专题 对称加密算法

    千次阅读 2021-11-16 18:02:06
    一般来说,使用OpenSSL对称加密算法有两种方式,一种是使用API函数的方式,一种是使用OpenSSL提供的对称加密算法指令方式。本书将介绍对称加密算法的指令方式 OpenSSL的对称加密算法指令主要用来对数据进行加密和...
    • 一般来说,使用OpenSSL对称加密算法有两种方式,一种是使用API函数的方式,一种是使用OpenSSL提供的对称加密算法指令方式。本书将介绍对称加密算法的指令方式
    • OpenSSL的对称加密算法指令主要用来对数据进行加密和解密处理输入输出的方式主要是文件,当然,也可以是默认的标准输入输出设备
    • OpenSSL基本上为所有其支持的对称加密算法都提供了指令方式的应用,这些应用指令的名字基本上都是以对称加密算法本身的名字加上位数、加密模式或其他属性组合而成。比如DES算法的CBC模式,其对应的指令就是des-cbc。
    • 要查找最新版本的OpenSSL支持哪些对称加密算法指令,只要在OpenSSL应用程序提示符下输入“-help”,就可以看到在输出信息最后部分(Ciphercommands)有很多我们熟悉的算法名称,这些就是OpenSSL支持的对称加密算法指令。OpenSSL还将所有的对称加密算法指令集成在一个指令程序中,那就是enc指令
    • enc指令是OpenSSL中对称加密算法指令的集大成者,用户可以在它的一个参数中指定使用哪种加密算法和模式,从而统一了对称加密算法指令的入口。enc指令的格式跟单独一个对称加密算法指令的格式是基本一样的,但是增加了一个算法类型的选择参数选项。
    • 比如,下面两种形式的指令是等价的:

    • OpenSSL的对称加密算法指令还可以增加BASE64编解码的功能,也就是说,可以在数据加密后将数据进行BASE64编码后输出保存,然后在解密的时候先将数据进行BASE64解码后再进行解密。这样,对于加密后数据的保存和处理就更加方便,因为BASE64编码将加密后的很多不可见字符都编码成可见的字符了。当然,如果你愿意,也可以单独使用BASE64编码的功能,OpenSSL为此也提供了专门的指令,其使用形式跟其他对称加密算法指令是一致的。
    • OpenSSL的对称加密算法指令还可以作为使用第三方加密库(通常是硬件加密设备)的应用接口,也就是说,它可以使用第三方的加密库作为完成加密操作的真正设备。这是通过OpenSSL的Engine机制实现的。当然,使用第三方加密库的前提是你已经安装了第三方的加密设备并成功通过Engine机制加载到了OpenSSL中。 
    • 不过,对OpenSSL的所有指令,包括对称加密算法指令,你不能期望过高,这些指令虽然功能强大,但是并没有支持所有可能的加密算法和模式,只是提供了固定的部分功能。比如对称加密算法指令就不支持76位的RC2加解密或者84位的RC4加解密等功能。如果你想使用这些灵活的加密模式和算法,那么就需要对OpenSSL进行进一步的深入研究,即使用OpenSSL的API。

     

    • 对于大部分块加密对称加密算法,OpenSSL都提供了CBC、CFB、ECB和OFB四种加密模式。需要注意的是,对于使用两个密钥和三个密钥EDE方式的三重DES算法,其ECB模式的指令名称并没有明确标出,很容易跟CBC模式混同,因为块加密算法使用最多的是CBC方式。 
    • 如果要单独使用BASE64编码而不进行数据的加密和解密,那么只要简单地忽略算法类型参数并加上“a”或者“base64”选项就可以了,当然,你如果不愿意忽略算法类型,也可以输入“-none”选项。下面三种形式是等价的,仅使用BASE64编码的指令:

    • 从表还可以看出,对于绝大部分对称加密算法来说,都有enc参数式的指令和单独的指令两种方式,它们都是等价的,至于选择哪一种,主要取决于用户本身的偏好。不过,enc指令可能会更快地支持新的对称加密算法,而单独的对称加密算法指令就不一定能得到及时的更新。这跟enc实现的机制是有关系的,因为enc使用的是OpenSSL内部定义的对称加密算法简称作为类型输入参数,只要是OpenSSL定义的对称加密算法模式,enc程序都能通过接口API自动支持,不需要因为增加了新的对称加密算法而进行enc应用程序的修改。 
    • 相对于其他指令来说,对称加密算法的指令参数比较少,使用起来也相对容易。对称 加密算法指令的参数形式如下:

    • iphername是在表7-1中第二列和第三列中出现的参数值之一。如果你选择第一种指令形式,那么就需要选择表7-1第二列的参数形式;如果你选择的是后一种独立对称加密算法指令方式,那就应该使用表7-1第三列的参数形式。对于第一种对称加密算法指令使用方式来说,如果你不需要进行任何加密或解密处理,那么可以输入none选项替代ciphername,当然,你也可以简单忽略ciphername选项,其效果是一样的。

    (2)in和out选项

    • 这两个选项分别用于指令输入和输出文件,对于加密操作来说,输入的应该是明文文件,也就是要加密的文件,输出的是密文文件,即经过加密的文件;对于解密操作来说,输入的是经过加密的文件,而输出的是恢复的明文文件。输入和输出文件名本身是没有任何限制的,只要符合习惯的文件名形式即可。需要注意的是,一般不要试图编辑和改变加密后的文件,那样做可能引起文件的部分甚至全部内容不能进行正确的解密!默认的输入和输出文件是标准输入和输出设备,对于Windows来说,就是指令行界面。需要注意的是,如果提供的输出文件名是已经存在的文件,那么程序会首先将该文件内容清空!

    (3)口令输入选项pass,k和kfile

    • 如果你不愿意输入繁杂的用来加密数据的密钥和初始向量,那么可以使用从口令中提取密钥和初始向量的方法。OpenSSL对称加密算法指令中输入口令的目的正在于此,事实上,OpenSSL中几乎所有输入的口令都是用作提取密钥的材料,而不是直接用作加密的密钥。pass选项提供了最灵活的口令输入方式,输入的源可以是标准输入设备、指令行直接输入、提示输入、文件、环境变量和文件描述符,具体的格式介绍读者可以参考7-4节的应用实例。k选项和kfile选项都是为了兼容以前的版本而保留的,它们的功能目前都可以使用pass选项来实现。k选项后面输入的参数是口令字符。kfile选项后面输入的参数是作为口令的文件名,当然,必要的时候应该也提供路径。OpenSSL的口令文件以第一行作为输入口令。

    (4)e和d选项

    • e和d选项分别表示执行加密操作(encryption)和解密操作(decryption),两个参数是互斥的,不能同时出现,但是可以同时不出现,这时候就执行默认的操作,即执行加密操作。这两个选项都不带参数。

    (5)base64,a和A选项

    • 选项a和base64的作用是相同的,就是将文件进行BASE64的编解码操作。对于加密操作来说,就在数据加密之后进行BASE64编码;对于解密操作来说,就在解密操作之前执行BASE64解码。A选项跟a或者base64选项一起使用才能生效,如果出示了A选项,则程序将努力将所有加密数据作为一行进行BASE64编码,而不是按照文件原有的换行格式进行BASE64编码。需要注意的是,在文件比较大的时候,A选项经常会导致指令执行失败。上述三个选项都不带参数。

    (6)K和IV选项

    • 如果你使用这两个选项,意味着你不相信OpenSSL从口令提取加密密钥和初始向量的方法,而使用自己直接提供的加密密钥和初始向量,那么这时候你就不再需要使用口令选项。K选项后面的参数是加密密钥,是以十六进制的方式表示,长度不能超过64个字符。IV选项只有在分组加密算法的某些模式才需要,其参数也是以十六进制的方式表示,长度不能超过32个字符。如果输入的参数不是十六进制的字符,那么程序就会报错。上述选项参数输入的长度如果不够,就在后面补零替代。

    (7)salt,nosalt和S选项

    • salt选项指明在从口令提取密钥的过程中使用盐值,这可以增强被加密数据的安全性,事实上,即便不出示此选项,默认指令也会使该选项生效。nosalt选项跟salt选项相反,告诉指令在密钥提取的过程中不使用盐值,一般来说,如果不是特别地为了跟OpenSSL一些老版本兼容,不要做这样降低安全性的事情。S选项后面的输入参数是十六进制编码的真正使用的盐值,其长度不能超过16个字符。所有这些选项只有跟口令输入选项一起使用才会生效,如果你使用K和IV选项方式输入加入密钥,那么这些选项将不会产生任何作用。

    (8)engine选项

    • 该选项的参数是OpenSSL支持的Engine的名称,一般是以字符串表示,比如“cswift”,“nuron”和“pkcs11”等。如果你不知道目前你的OpenSSL支持的Engine特征字符串,可以输入下列指令,其中有效的Engine都会提示出来:
    • OpenSSL>engine -t
    • 如果你使用了有效的Engine,那么你所执行的加密操作实际上都是在第三方加密设备中执行,而不再是使用OpenSSL密码库的软件算法。

    (9)p和P选项

    • p选项打印出对称加密算法真正使用的加密密钥和初始向量,输出的格式是十六进制的形式。如果出示了P选项,则程序在打印出加密密钥和初始向量后就立刻退出,而不执行真正的加密或解密操作。

    (10)nopad,bufsize和debug选项

    • 这几个选项之间其实并没有联系,这里之所以放在一起,只是为了节省篇幅。nopad选项指定不使用默认的PKCS#5标准的补丁方式,如果这样做,那么就要确保在块加密算法中输入的数据是加密块长度的整数倍,比如使用DES算法,就要保证输入的数据是8字节的整数倍。
    • bufsize选项的参数指定了读写文件的I/O缓存,指定的数字以字节为单位,也可以在数字后面加“k”表示是以1024字节为单位。比如,下面的格式都是可以被接受的:
    • -bufsize 256 或者 -bufsize 8k
    • 如果你指定的缓存小于80字节,指令程序会自动将它增加为80字节,这是进行BASE64一行编码所需要的最小长度。
    • 使用debug选项后,OpenSSL的对称加密算法指令会将整个执行过程中I/O操作相关的BIO列出来。这主要是为了调试目的而使用,对于一般用户来说,该选项很少使用。

    例子

    • 本节将给出对称加密算法指令的一些具体实例,在下面的例子中,“pln.txt”表示明文文件,“enc.txt”表示经过加密的密文文件,而“rcv.txt”表示恢复的明文文件。
    • 下面指令将文件pln.txt的内容复制到文件enc.txt中:

    • 使用的时候 需要指定文件的绝对路径 

    •  OpenSSL对称加密算法加密数据的时候需要使用密钥,对于块加密算法的某些模式,还需要初始向量,既可以直接输入加密密钥和初始向量,也可以通过口令来提取加密密钥和初始向量
    • 就口令输入来说,也有多种不同的方式,本节将给出多种输入口令和密钥的例子。
    • 下面是DES算法CBC模式指令直接使用加密密钥和初始向量的例子:

    展开全文
  • 用非对称相似关系代替粗糙理论中的等价关系,定义了非对称相似差别矩阵,提出了基于非对称相似差别矩阵的高效求核和知识约简算法。该算法无需改变初始不完备信息系统的结构,能直接处理缺省数据。实验结果表明,新...
  • 定义2 设有一个r行s列的离散无记忆信道的信道矩阵P,根据信道的输出Y可以将P分成n个子矩阵 P 1 , P 2 , ⋯ , P n ,每个子矩阵对应的信道都是对称信道,称这个信道为准对称信道 [1] 。 定义3信道容量 C = max p ...
  • 首先在区间直觉模糊近似空间中,定义了一对具有对称性的新的区间直觉模糊上、下近似算子;其次给出了区间直觉模糊粗糙隶属函数的定义并讨论了相关性质;最后利用区间直觉模糊粗糙隶属函数的区间直觉模糊熵,定义了...
  • 在每一个层次中,利用非对称相似关系定义相似类,进而定义集合的上近似、下近似、近似精度和粗糙度等概念.在不同层次之间,分别讨论了上近似、下近似、近似精度和粗糙度的性质,在不同的知识粒度下探索的知识近似的变化...
  • 对称密钥算法与非对称密钥算法

    万次阅读 多人点赞 2019-03-18 15:08:48
    对称加密:速度高,可...1.定义对称加密算法即,加密和解密使用相同密钥的算法。(加密Key=解密key);对称密钥算法又分为分组密码 (Block Cipher)和流密码(Stream Cipher)。 常用算法包括DES(Data Encryption S...
  • Symmetric KL-divergence(SKL,即对称KL散度)计算如下 从SKL的概念出发,我们可以定义对称交叉熵 Symmetric Cross Entropy (SCE) 是逆交叉熵(Reverse Cross Entropy) 则在样本分类任务中,新的损失函数可以定义...
  • 集合论—关系的自反、对称和传递闭包

    万次阅读 多人点赞 2019-06-21 21:52:33
    关系的自反、对称和传递闭包定义 设R\text{R}R是非空集合AAA上的关系,R\text{R}R的自反(对称、传递)闭包是AAA上的关系R′\text{R}&#x27;R′,且R′\text{R}&#x27;R′满足以下条件: R′\text{R}&#...
  • 博文首先贴出交集、并集、差集、对称差运算的C++代码以及程序运行结果,然后再进行一个比较完整的构建代码思路解析,整个项目的实现功能如下: 文章目录 1. 实现代码以及程序运行结果 1.1 头文件定义 UFSets.h 1.2 ...
  • 定义了基于相关的频繁术语,以进一步扩展术语。 同时,将信息增益引入到传统的TF-IDF中,更好地表达了类别分布信息,并增强了每个类别的单词权重。 提取所有具有外部关系的术语对,并扩展常用术语。 最后,...
  • 在本文中,我们一起学习如何将机器学习应用于癌症数据。 1.摘要 支持向量机(SVM)是机器学习中最流行的有监督学习算法之一。许多研究人员都通过实践证明了该算法的优异性。 SVM既可以应用于回归问题,也可以应用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 50,665
精华内容 20,266
关键字:

对称集定义