文章目录
一、关系矩阵
二、关系矩阵示例
三、关系矩阵性质
四、关系矩阵运算
五、关系图
六、关系图示例
七、关系表示相关性质









一、关系矩阵



$A = \{ a_1, a_2 , \cdots , a_n \} , R \subseteq A \times A$
$R$ 使用 关系矩阵 表示 : $M(R) = (r_{ij})_{n\times n}$
关系矩阵取值 : $M(R)(i, j) = r_{ij} =\begin{cases} 
1,  & a_i R a_j \\
0, & 无关系
\end{cases}$


关系矩阵定义说明 :
$A$ 是个 $n$ 元集 ( 集合中有 $n$ 个元素 ) , $R$ 是$A$ 上的二元关系 , $R$ 的关系矩阵是 $n \times n$ 的方阵 , 第 $i$ 行第 $j$ 列位置的元素 $r_{ij}$ 取值只能是 $0$ 或 $1$ ;


关系矩阵取值说明 :
如果 $r_{ij} = 1$ , 则说明 $A$ 集合中 第 $i$ 个元素与第 $j$ 个元素具有关系 $R$ , 记作 : $a_i R a_j$ ;
如果 $r_{ij} = 0$ , 则说明 $A$ 集合中 第 $i$ 个元素与第 $j$ 个元素没有关系 $R$ ;


关系矩阵本质 : 关系矩阵中 , 每一行对应着 $A$ 集合中的元素 , 每一列也对应着 $A$ 集合中的元素 , 行列交叉的位置的值 ( $0$ 或 $1$ ) 表示 $A$ 集合中第 $i$ 个元素与第 $j$ 个元素构成的有序对是否有关系 $R$ ;








二、关系矩阵示例



$A = \{ a, b, c \}$
$R_1 = \{ <a, a>, <a,b> , <b,a> , <b,c> \}$
$R_2 = \{ <a,b> , <a,c> , <b,c> \}$


使用关系矩阵表示上述 $R_1 , R_2$ 两个关系 :




$R_1 = \{ <a, a>, <a,b> , <b,a> , <b,c> \}$ 其中 :

$<a, a>$ : $a$ 是第 $1$ 个元素 , $a$ 是第 $1$ 个元素 , 第 $1$ 行第 $1$ 列元素是 $1$
$<a, b>$ : $a$ 是第 $1$ 个元素 , $b$ 是第 $2$ 个元素 , 第 $1$ 行第 $2$ 列元素是 $1$
$<b, a>$ : $b$ 是第 $2$ 个元素 , $a$ 是第 $1$ 个元素 , 第 $2$ 行第 $1$ 列元素是 $1$
$<b, c>$ : $b$ 是第 $2$ 个元素 , $c$ 是第 $3$ 个元素 , 第 $2$ 行第 $3$ 列元素是 $1$
其余全是 $0$

$M(R_1) = \begin{bmatrix}
1      & 1 & 0      \\\\
1 & 0 & 1 \\\\
0      & 0 & 0
\end{bmatrix}$




$R_2 = \{ <a,b> , <a,c> , <b,c> \}$ 其中 :

$<a, b>$ : $a$ 是第 $1$ 个元素 , $b$ 是第 $2$ 个元素 , 第 $1$ 行第 $2$ 列元素是 $1$
$<a, c>$ : $a$ 是第 $1$ 个元素 , $c$ 是第 $3$ 个元素 , 第 $1$ 行第 $3$ 列元素是 $1$
$<b, c>$ : $b$ 是第 $2$ 个元素 , $c$ 是第 $3$ 个元素 , 第 $2$ 行第 $3$ 列元素是 $1$
其余全是 $0$

$M(R_2) = \begin{bmatrix}
0  & 1   & 1      \\\\
0   & 0   & 1      \\\\
0   & 0   & 0
\end{bmatrix}$








三、关系矩阵性质



有序对集合表达式 与 关系矩阵 可以唯一相互确定




性质一 : 逆运算相关性质
$M(R^{-1}) = (M(R))^T$


$M(R^{-1})$ 关系的逆 的 关系矩阵

与

$(M(R))^T$ 关系矩阵 的 逆

这两个矩阵是相等的 ;




性质二 : 合成运算相关性质
$M(R_1 \circ R_2) = M(R_2) \bullet M(R_1)$
$\bullet$ 是矩阵的 逻辑乘法 , 计算 矩阵 $r_{ij}$ 的值 第 $i$ 行 乘以 第 $j$ 列 , 逐位 逻辑相乘 , 再将逻辑相乘结果再 逻辑相加 ;
上述 逻辑乘法使用 $\land$ 运算 , 逻辑加法使用 $\lor$ 运算 ;








四、关系矩阵运算



$A = \{ a, b, c \}$
$R_1 = \{ <a, a>, <a,b> , <b,a> , <b,c> \}$
$R_2 = \{ <a,b> , <a,c> , <b,c> \}$


在上面的示例中 , 已经求出两个关系矩阵 ;
$M(R_1) = \begin{bmatrix}
1      & 1 & 0      \\\\
1 & 0 & 1 \\\\
0      & 0 & 0
\end{bmatrix}$  , $M(R_2) = \begin{bmatrix}
0  & 1   & 1      \\\\
0   & 0   & 1      \\\\
0   & 0   & 0
\end{bmatrix}$




1. 求 $M(R^{-1}) , M(R_2^{-1})$
直接将矩阵转置 , 即可获取 关系的逆的关系矩阵 ;
$M(R_1^{-1}) = (M(R_1))^T = \begin{bmatrix}
1      & 1 & 0      \\\\
1 & 0 & 0 \\\\
0      & 1 & 0
\end{bmatrix}$
$M(R_2^{-1}) = (M(R_2))^T = \begin{bmatrix}
0      & 0 & 0      \\\\
1 & 0 & 0 \\\\
1      & 1 & 0
\end{bmatrix}$
$R_1^{-1} = \{ <a, a> , <a, b> , <b,a> , <c,b> \}$
$R_2^{-1} = \{ <b, a> , <c,a> , <c,b> \}$




2. 求 $M( R_1 \circ R_1 )$
$M( R_1 \circ R_1 ) = M(R_1) \bullet M(R_1)$
其中的 $\bullet$ 是两个矩阵的逻辑乘法 , 加法使用 $\lor$ , 乘法使用 $\land$
$M(R_1) \bullet M(R_1) = \begin{bmatrix}
1      & 1 & 0      \\\\
1 & 0 & 1 \\\\
0      & 0 & 0
\end{bmatrix} \bullet \begin{bmatrix}
1      & 1 & 0      \\\\
1 & 0 & 1 \\\\
0      & 0 & 0
\end{bmatrix} = \begin{bmatrix}
1      & 1 & 1      \\\\
1 & 1 & 0 \\\\
0      & 0 & 0
\end{bmatrix}$
矩阵的逻辑乘法 : 结果矩阵的第 $i$ 行 , 第 $j$ 列元素的值为 , 第 $i$ 行的三个元素 分别与上第 $j$ 列的三个元素 , 然后三个结果进行或运算 , 最终结果就是 矩阵的第 $i$ 行 , 第 $j$ 列元素的值 ;
$R_1 \circ R_1 = \{ <a,a> , <a,b> , <a,c> , <b,a>, <b,b> \}$




3. 求 $M( R_1 \circ R_2 )$
$M( R_1 \circ R_2 ) = M(R_2) \bullet M(R_1)$
其中的 $\bullet$ 是两个矩阵的逻辑乘法 , 加法使用 $\lor$ , 乘法使用 $\land$
特别注意 , 合成的顺序是逆序合成 , 后者关系矩阵在前 , 前者关系矩阵在后
$M(R_1) \bullet M(R_2) =\begin{bmatrix}
0  & 1   & 1      \\\\
0   & 0   & 1      \\\\
0   & 0   & 0
\end{bmatrix} \bullet   \begin{bmatrix}
1      & 1 & 0      \\\\
1 & 0 & 1 \\\\
0      & 0 & 0
\end{bmatrix}  = \begin{bmatrix}
1      & 0 & 1      \\\\
0 & 0 & 0 \\\\
0      & 0 & 0
\end{bmatrix}$
矩阵的逻辑乘法 : 结果矩阵的第 $i$ 行 , 第 $j$ 列元素的值为 , 第 $i$ 行的三个元素 分别与上第 $j$ 列的三个元素 , 然后三个结果进行或运算 , 最终结果就是 矩阵的第 $i$ 行 , 第 $j$ 列元素的值 ;
$R_1 \circ R_2 = \{ <a,a>, <a,c> \}$








五、关系图



$A = \{ a_1, a_2 , \cdots , a_n \} , R \subseteq A \times A$
$R$ 的关系图 :

顶点 : $\circ$ 表示 $A$ 集合中的元素 ;
有向边 : $\rightarrow$ 表示 $R$ 中的元素 ;
$a_i R a_j$ 就是从顶点 $a_i$ 到 顶点 $a_j$ 的有向边 $<a_i , a_j>$ ;









六、关系图示例



$A = \{ a, b, c \}$


$R_1 = \{ <a, a> , <a,b> , <b,a> , <b,c> \}$ 关系图表示方式 :




$R_2 = \{ <a,b>, <a,c>, <b,c> \}$ 使用关系图表示 :



$R_1^{-1} = \{ <a,a>, <a,b>, <b,a> , <c,b> \}$



$R_2^{-1} = \{ <b,a> , <c,a> , <c,b> \}$









七、关系表示相关性质



$A$ 集合中的元素 , 标定次序后 , 即生成了 $A$ 上的关系 , $R \subseteq A \times A$ , 有如下性质 :

关系图 $G(R)$ 与 关系的 $R$ 的集合表达式 ( 有序对集合 ) , 可以 唯一确定 ;
关系 $R$ 的集合表达式 , 关系矩阵 $M(R)$ , 关系图 $G(R)$ , 都是一一对应的 ;



$R \subseteq A \times B$

集合 $A$ 中有 $n$ 个元素 , $|A| = n$
集合 $B$ 中有 $m$ 个元素 , $|B| = m$
关系矩阵 $M(R)$ 是 $n \times m$ 阶矩阵 ;
关系图 $G(R)$ 有向边都是从 $A$ 集合中的元素 指向 $B$ 集合中的元素

正定矩阵

在线性代数里，正定矩阵 (positive definite matrix) 有时会简称为正定阵。 
定义:A是n阶方阵，如果对任何非零向量x，都有xTAx>0，其中xT 表示x的转置，就称A正定矩阵。

性质:

正定矩阵的行列式恒为正；
实对称矩阵A正定当且仅当A与单位矩阵合同；
两个正定矩阵的和是正定矩阵；
正实数与正定矩阵的乘积是正定矩阵。
等价命题: 

对于n阶实对称矩阵A，下列条件是等价的：

A是正定矩阵；
A的一切顺序主子式均为正；
A的一切主子式均为正；
A的特征值均为正；
存在实可逆矩阵C，使A=C'C；
存在秩为n的m×n实矩阵B，使A=B'B；
存在主对角线元素全为正的实三角矩阵R，使A=R'R
根据正定矩阵的定义及性质，判别对称矩阵A的正定性有两种方法：

求出A的所有特征值。若A的特征值均为正数，则A是正定的；若A的特征值均为负数，则A为负定的。
计算A的各阶顺序主子式。若A的各阶顺序主子式均大于零，则A是正定的；若A的各阶顺序主子式中，奇数阶主子式为负，偶数阶为正，则A为负定的。


  
例： 判断矩阵是否正定
Q=⎧⎩⎨⎪⎪6−31−320104⎫⎭⎬⎪⎪


  解：对称矩阵Q的三个顺序主子式依次为 
|6|=6>0

∣∣∣6−3−32∣∣∣=3>0

∣∣∣∣6−31−320104∣∣∣∣=10>0


  矩阵Q是正定的

半正定矩阵

设A是实对称矩阵。如果对任意的实非零列向量x有xTAx≥0，就称A为半正定矩阵。 

对于半正定矩阵来说，相应的条件应改为所有的主子式非负。顺序主子式非负并不能推出矩阵是半正定的。 
性质:

半正定矩阵的行列式是非负的；
两个半正定矩阵的和是半正定的；
非负实数与半正定矩阵的数乘矩阵是半正定的。
等价条件:

A是半正定的；
A的所有主子式均为非负的；
A的特征值均为非负的；
存在n阶实矩阵C，使A=C'C；
存在秩为r的r×n实矩阵B，使A=B'B。
直观理解正定、半正定矩阵:

XTMX≥0
XTY≥0  (Y=MX)
cos(θ)=XTY||X||∗||Y||≥0

||X||, ||Y||代表向量 X,Y的长度，\theta是他们之间的夹角。正定、半正定矩阵的直觉代表一个向量经过它的变化后的向量与其本身的夹角小于等于90度。

题目描述

给定有限集合上二元关系的关系矩阵，利用传递闭包的定义式（不是warshall算法）求其传递闭包的关系矩阵。

源代码
#include<stdio.h>
#define N 100
int mult(int a[N][N],int b[N][N],int n,int c[N][N])
{
	int i,j,k;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			c[i][j]=0;
		}
	}//每次接收矩阵乘积前先初始化为0 
	for(i=0;i<n;i++)  
	{   
		for(j=0;j<n;j++)  
		{    
			for(k=0;k<n;k++)    
			{     
				c[i][j]+=a[i][k]*b[k][j];    
			}   
		}  
	}
}//定义实现矩阵乘法的函数 
int main()
{
	int n,a[100][100]={0},i,j,k,b[100][100]={0},c[100][100]={0},d[100][100]={0};
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			scanf("%d",&a[i][j]);
			b[i][j]=a[i][j];
			d[i][j]=a[i][j];
		}
	}//输入邻接矩阵，并用另一个矩阵暂时存储 
	for(i=0;i<n-1;i++)
	{
		mult(a,b,n,c);
		for(j=0;j<n;j++)
		{
			for(k=0;k<n;k++)
			{
				b[j][k]=c[j][k];//用c来接收前两个矩阵相乘的结果，并将其储存在b中以实现求解高次矩阵 
				d[j][k]+=c[j][k];
			}
		}
	} 
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(i==j) d[i][j]=1;
			else if(i!=j&&d[i][j]>0)
			{
				d[i][j]=1;
			}
		}
	}//将矩阵d转化为布尔矩阵 
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			printf("%d ",d[i][j]);
		}
		printf("\n");
	}
}

        
                

                    
1.正定矩阵和半正定矩阵
 
若所有特征值均大于零，则称为正定。
 
定义:A是n阶方阵，如果对任何非零向量x，都有>0,其中表示x的转置，就称A为正定矩阵。
 
性质:
 
正定矩阵的行列式恒为正；
实对称矩阵AA正定当且仅当AA与单位矩阵合同；
两个正定矩阵的和是正定矩阵；
正实数与正定矩阵的乘积是正定矩阵。
根据正定矩阵的定义及性质，判别对称矩阵A的正定性有两种方法：
 
求出A的所有特征值。若A的特征值均为正数，则A是正定的；若A的特征值均为负数，则A为负定的。
 
计算A的各阶顺序主子式。若A的各阶顺序主子式均大于零，则A是正定的；若A的各阶顺序主子式中，奇数阶主子式为负，偶数阶为正，则A为负定的。
 
 
2.半正定矩阵
 
若所有特征值均不小于零，则称为半正定。
 
定义：设A是实对称矩阵。如果对任意的实非零列向量x有≥0，就称A为半正定矩阵。 
 
对于半正定矩阵来说，相应的条件应改为所有的主子式非负。顺序主子式非负并不能推出矩阵是半正定的。 
 性质:
 
半正定矩阵的行列式是非负的；
两个半正定矩阵的和是半正定的；
非负实数与半正定矩阵的数乘矩阵是半正定的。