线性代数相关笔记

这篇具有很好参考价值的文章主要介绍了线性代数相关笔记。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

线性基

导入

线性基,顾名思义,就是一个包含数字最少的集合,使得原集合中的任何数都能用线性基中的元素表示。

集合中的元素满足一些性质:

  • 原集合中的任意元素都可以用线性基中的若干元素的异或和表示
  • 线性基中任意数异或和不为 0 0 0,否则不满足集合大小最小
  • 以任意顺序枚举原集合中元素,所得集合大小相同
  • 大小为 n n n 的线性基可以表示 2 n 2^n 2n 个数;若线性基中存在二进制第 i i i 位为 1 1 1 的数,则可以表示 2 n − 1 2^{n-1} 2n1 个二进制下第 i i i 位为 1 1 1 的数。

操作

插入

我们用数组 p 表示线性基,假设要插入 x x x,从高到低枚举 x x x 的二进制的每一位数字,如果 x x x 的第 i i i 位为 1 1 1 p i = 0 p_i=0 pi=0,那么令 p i = x p_i=x pi=x 并结束插入;否则,令 x^=p[i],继续枚举下一位。

void insert(int x)
{
    for(int i=50;i>=0;--i)
        if(x>>i&1)
        {
            if(!p[i]) {p[i]=x;break;}
            else x^=p[i];
        }
}

求异或最大值

求原集合的子集的异或最大值,利用贪心思想。若 ans^p[i]>ans,则 ans^=p[i]

int pmax()
{
    int ans=0;
    for(int i=50;i>=0;--i)
		if((ans^p[i])>ans) ans^=p[i];
	return ans;
}

求异或最小值

分两种情况考虑:

  • 线性基大小 < < < 原集合大小:原集合中一定存在异或和为 0 0 0 的一些数,所以异或最小值为 0 0 0
  • 线性基大小 = = = 原集合大小:在线性基内求异或最小值,线性基内的最小元素与其他元素异或得到的值一定更大,所以异或最小值为线性基中最小元素。

剩的异或 k k k 小值先咕了 QwQ 本来学线性基是想过 YbtOJ 的最大异或对的,结果发现线性基是任意数的最大异或和,这一道题是一对,只能用 trie 树


练手板子题

代码如下:

#include <bits/stdc++.h>
using namespace std;
#define int long long

int p[55];

void insert(int x)
{
    for(int i=50;i>=0;--i)
        if(x>>i&1)
        {
            if(!p[i]) {p[i]=x;break;}
            else x^=p[i];
        }
}

int pmax()
{
    int ans=0;
    for(int i=50;i>=0;--i)
		if((ans^p[i])>ans) ans^=p[i];
	return ans;
}

signed main()
{
	int n,x;cin>>n;
	for(int i=1;i<=n;i++) cin>>x,insert(x);
	cout<<pmax();
	return 0;
}

行列式

行列式,是一种对于矩阵的特殊形式——方阵的表示形式。所谓方阵,就是 n × n n\times n n×n的矩阵。

一个 n × n n\times n n×n 的方阵 A A A 的行列式记为 det ⁡ ( A ) \det(A) det(A) 或者 ∣ A ∣ |A| A,一个 2 × 2 2\times2 2×2 矩阵的行列式可表示如下:
det ⁡ ( a b c d ) = a d − b c \det \begin{pmatrix} a&b\\ c&d \end{pmatrix}=ad-bc det(acbd)=adbc
把一个 n n n 阶行列式中的元素 a i j a_{ij} aij 所在的第 i i i行和第 j j j列划去后,留下来的 n − 1 n-1 n1 阶行列式叫做元素 a i j a_{ij} aij 的余子式,记作 M i j M_{ij} Mij。记 A i j = ( − 1 ) i + j M i j A_{ij}=(-1)^{i+j}M_{ij} Aij=(1)i+jMij,叫做元素 a i j a_{ij} aij 的代数余子式。

一个 n × n n\times n n×n 矩阵的行列式等于其任意行(或列)的元素与对应的代数余子式乘积之和,即:
det ⁡ ( A ) = a i 1 A i 1 + ⋯ + a i n + A i n = ∑ j = 1 n a i j ( − 1 ) i + j det ⁡ ( A i j ) \det(A)=a_{i1}A_{i1}+\cdots+a_{in}+A_{in}=\sum_{j=1}^na_{ij}(-1)^{i+j}\det(A_{ij}) det(A)=ai1Ai1++ain+Ain=j=1naij(1)i+jdet(Aij)
代码实现:

int dett(int a[maxn][maxn],int n)//n为阶数
{
    int dett=0,k=0,h=0;
    if(n==1) return a[0][0];
    else if(n==2) return a[0][0]*a[1][1]-a[0][1]*a[1][0];
    else
    {
        for(int p=0;p<n;p++)
        {
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                {
                    if(j==p) continue;
                    tmp[h][k]=a[i][j],k++;
                    if(k==n-1) h++,k=0;
                }
            dett=dett+a[0][p]*pow(-1,p)*det(tmp,n-1)
        }
        return dett;
    }
}

高斯消元

前置芝士

三角矩阵

上三角矩阵的对角线左下方的系数全部为 0 0 0,下三角矩阵的对角线右上方的系数全部为 0 0 0。三角矩阵可以看作是一般方阵的一种简化情形。由于带三角矩阵的矩阵方程容易求解,在解多元线性方程组时,总是将其系数矩阵通过初等变换化为三角矩阵来求解。

举个栗子,下面的矩阵 U U U 就是一个上三角矩阵。
U = [ u 1 , 1 u 1 , 2 u 1 , 3 ⋯ u 1 , n 0 u 2 , 2 u 2 , 3 ⋯ u 2 , n 0 0 ⋱ ⋱ ⋮ ⋮ ⋮ 0 ⋱ u n − 1 , n 0 0 ⋯ 0 u n , n ] U= \begin{bmatrix} u_{1,1}&u_{1,2}&u_{1,3}&\cdots&u_{1,n}\\ 0&u_{2,2}&u_{2,3}&\cdots&u_{2,n}\\ 0&0&\ddots&\ddots&\vdots\\ \vdots&\vdots&0&\ddots&u_{n-1,n}\\ 0&0&\cdots&0&u_{n,n} \end{bmatrix} U= u1,1000u1,2u2,200u1,3u2,300u1,nu2,nun1,nun,n

增广矩阵

又称扩增矩阵,就是在系数矩阵的右边添上一列,这一列是线性方程组的等号右边的值。

高斯消元

基本思想

通过一系列的加减消元运算,将方程组化为上三角矩阵。然后再逐一回代求出 x x x

实现过程

解方程:
{ 3 x 1 + 2 x 2 + x 3 = 6 2 x 1 + 2 x 2 + 2 x 3 = 4 4 x 1 − 2 x 2 − 2 x 3 = 2 \begin{cases} 3x_1+2x_2+x_3=6\\ 2x_1+2x_2+2x_3=4\\ 4x_1-2x_2-2x_3=2 \end{cases} 3x1+2x2+x3=62x1+2x2+2x3=44x12x22x3=2
我们把这个方程组写成增广矩阵的形式:文章来源地址https://www.toymoban.com/news/detail-737640.html

到了这里,关于线性代数相关笔记的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【线性代数】向量组的线性相关性

    目录 一、图解向量组的线性相关性 1. 向量组线性相关的定义  2.三维空间中向量组线性相关的几何意义 3.向量组线性相关与齐次线性方程组 二、向量组线性相关的基本结论 三、向量组线性相关性总结 做出向量组A与向量组B的图如下: 旋转图形得到:  旋转后发现,向量组

    2024年02月04日
    浏览(44)
  • 线性代数——行列式相关性质

    目录 一、行列式与它的转置列行列式相等 二、对换行列式的两行(列),行列式变号  三、行列式某行(列)有公因子k,则k可以提到行列式外 四、行列式中若两行成比例,则行列式为0 五、行列式的某一行(列)的元素都是两数之和,则  六、将行列式的某行(列)元素乘

    2024年01月19日
    浏览(55)
  • 线性代数相关书籍读后感

    读《上帝掷骰子吗》有感 最初拿到书的我是很迷茫的,不明白上帝掷骰子与量子力学有什么关联。了解后才发现,上帝掷骰子吗这个问题的答案体现的正是当时物理学俩大阵营的态度,以爱因斯坦为首的决定论坚守“上帝是不会掷骰子”,而以玻尔为首的哥本哈根派以“别指

    2024年04月11日
    浏览(32)
  • 线性代数第四章 向量组的线性相关性

    一.向量、向量组 1.向量 n个有次序的数a1,a2,...,an所组成的数组称为n维向量,这n个数称为该向量的n个分量,第i个数ai称为第 i个分量 n维向量可以写成一行,也可以写成一列, 在没有指明是行向量还是列向量时,均为列向量 2.向量组 若干个同维数的列向量(行向量)所组成的

    2024年02月10日
    浏览(49)
  • 计算机图形学线性代数相关概念

    Scale(缩放) [ x ′ y ′ ] = [ s 0 0 s ] [ x y ] (等比例缩放) left[ begin{matrix} x\\\' \\\\ y\\\' end{matrix} right]= left[ begin{matrix} s 0 \\\\ 0 s end{matrix} right] left[ begin{matrix} x \\\\ y end{matrix} right] tag{等比例缩放} [ x ′ y ′ ​ ] = [ s 0 ​ 0 s ​ ] [ x y ​ ] ( 等比例缩放 ) [ x ′ y ′ ] = [ s x 0 0 s y ] [ x

    2024年02月10日
    浏览(46)
  • 线性代数的学习和整理8:行列式相关

    目录 1 从2元一次方程组求解说起 1.1 直接用方程组消元法求解 1.2 有没有其他方法呢?有:比如2阶行列式方法 1.3  3阶行列式 2 行列式的定义 2.1 矩阵里的方阵 2.2  行列式定义:返回值为标量的一个函数 2.3 行列式的计算公式 2.4 克拉默法则 2.4.1 克拉默法则的内容 2.4.2 克拉默

    2024年02月11日
    浏览(41)
  • 线性代数:齐次线性方程组学习笔记

    齐次线性方程组是指所有方程的常数项均为零的线性方程组,即形如 A x = 0 Ax=0 A x = 0 的方程组。 其中,矩阵 A A A 是一个 m × n m times n m × n 的矩阵,向量 x x x 是一个 n n n 维列向量, 0 mathbf{0} 0 是一个 m m m 维零向量。 齐次线性方程组有以下性质: 1. 性质1 齐次线性方程组的

    2024年01月20日
    浏览(49)
  • 线性代数的学习和整理20,关于向量/矩阵和正交相关,相似矩阵等

    目录 1 什么是正交 1.1 正交相关名词 1.2 正交的定义 1.3 正交向量 1.4 正交基 1.5 正交矩阵的特点 1.6 正交矩阵的用处 orthogonal set 正交向量组 正交变换 orthogonal matrix 正交矩阵 orthogonal basis 正交基 orthogonal decomposition 正交分解 正交的定义:内积为0 正交一定线性无关 其实不共线也

    2024年02月09日
    浏览(57)
  • 线性代数的学习和整理8: 方阵和行列式相关(草稿-----未完成)

    目录 1 从2元一次方程组求解说起 1.1 直接用方程组消元法求解 1.2 有没有其他方法呢?有:比如2阶行列式方法 1.3  3阶行列式 2 行列式的定义 2.1 矩阵里的方阵 2.2  行列式定义:返回值为标量的一个函数 2.3 行列式的计算公式 2.4 克拉默法则 2.4.1 克拉默法则的内容 2.4.2 克拉默

    2024年02月12日
    浏览(44)
  • 线性代数笔记

    1、性质一:D= 注:是把D的行转为了列。 2、性质二:任意 两行或两列 互换,D=-D1         推论: 若行列式有 两行或两列 相同,则该行列式的值为0。 3、性质三: 行列式的某 一行或一列 的公因子可提到外面。         推论:若行列式 有两行 成比例  ,则行列式的值为

    2024年02月04日
    浏览(32)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包