10.1 信息系统的数学表示
根据信息定律 II,不确定性来自于:
(1)对象的运动;
(2)不同对象的相互作用。
一个信息系统就是由很多对象及这些对象的运动和相互作用构成的系统。
信息系统的直观数学模型就是图。
定义 10.1(信息系统图模型)一个信息系统就是一个图 𝐺 = (𝑉, 𝐸, 𝑓),满足如下性质:
(1)𝑉 是顶点集,其中一个顶点代表一个对象;
(2)𝐸 是形如 𝑒 = (𝑖, 𝑗) 的有向边构成的集合;
(3)对于每一个边 𝑒 = (𝑖, 𝑗) ∈ 𝐸,𝑓(𝑒) = 𝑓(𝑖, 𝑗) > 0,称为 𝑖对 𝑗 的交互分值 (interactive profile),这里交互分值 𝑓(𝑒) = 𝑓(𝑖, 𝑗)直观地表示对象 𝑖 对对象 𝑗 的作用力,或影响力,或者从 𝑖 到 𝑗
运动的概率,或者对象 𝑖 和对象 𝑗 的相似性; 对 𝑒 = (𝑖, 𝑗) ∉ 𝐸,则
𝑓(𝑒) = 𝑓(𝑖, 𝑗) = 0。
给定一个信息系统 𝐺 = (𝑉, 𝐸, 𝑓),固定 𝑉 中顶点的一个顺序如
𝑉 在下列集合中排列的顺序:
𝑉 = {1,2, ⋯ , 𝑛}.
对于 𝑖, 𝑗 ∈ {1,2, ⋯ , 𝑛},定义 𝑎𝑖𝑗 = 𝑓(𝑖, 𝑗),则得到非负矩阵 𝐴 = (𝑎𝑖𝑗),称 𝑨 为 𝑮 的一个矩阵,记为 𝐴 = 𝐴𝐺。
这就给出如下定义:
一个 𝑛 × 𝑛 的矩阵 𝐴 = (𝑎𝑖𝑗),使得对任意 𝑖, 𝑗,𝑎𝑖𝑗 ≥ 0, 记为 𝐴 ≥ 0.
令 𝐼𝑛×𝑛 是 𝑛 × 𝑛 的单位矩阵。一个置换矩阵是从 𝐼 出发,对一系列对 (𝑖, 𝑗),同时交换 𝑖, 𝑗 行和 𝑖, 𝑗 列所得到的矩阵。
假设 𝐴 是一个 𝑛 × 𝑛 非负矩阵,𝑃 是某一个 𝑛 阶置换矩阵,称 𝐵 = 𝑃𝑇𝐴𝑃 是 𝐴 的一个对称置换。
对于一个信息系统 𝐺 = (𝑉, 𝐸, 𝑓),假设 𝐴 是 𝐺 的一个矩阵,则任何一个 𝐴 的对称置换 𝐵 都是 𝐺 的一个矩阵。
𝐺 的一个对称置换就是对顶点集 𝑉 的一个排序下所定义的 𝐺
的矩阵。
一个以图模型定义的信息系统有很多矩阵,但所有这些矩阵表示的实质仍然是原来给定的图。
另一方面,对任给一个 𝑛 × 𝑛 非负矩阵 𝐴,令 𝑉 为 𝐴 的行的
指标集,对 𝑖, 𝑗 定义 𝑓(𝑖, 𝑗) = 𝑎𝑖𝑗 , 𝐸 = {(𝑖, 𝑗)|𝑎𝑖𝑗 > 0} ,则 𝐺 = (𝑉, 𝐸, 𝑓) 就是由非负矩阵 𝑨 定义的图,它表示一个信息系统,记为
𝐺 = 𝐺𝐴 。
显然,一个非负矩阵对应一个图,但一个图对应很多非负矩阵。表示信息系统的图是有向图。称一个有向图是强连通的,如果对
任何顶点 𝑥, 𝑦,有一条从 𝑥 到 𝑦 的应用 𝐺 中有向边的路径;否则称它为非强连通的。
对于一个 𝑛 × 𝑛 的非负矩阵 𝐴,如果存在 𝑛 阶置换矩阵 𝑃,使
得
𝑃𝑇𝐴𝑃 = [𝑋 𝑌],
0 𝑍
这里 𝑋, 𝑍 为方阵,则称 𝐴 是可约矩阵(reducible matrix)。如果 𝐴 不是可约矩阵,则称 𝐴 为不可约矩阵。
容易证明:对任意 𝑛 × 𝑛 非负矩阵 𝐴,𝐴 不可约当且仅当矩阵
𝐴 确定的图 𝐺 = 𝐺𝐴 是强连通图。
这提供了一个简单算法来判断一个给定的 𝑛 × 𝑛 非负矩阵是否为不可约矩阵。
对 于 一 个 不 可 约 非 负 矩 阵 𝐴 = 𝐴𝑛×𝑛 = (𝑎𝑖𝑗) ,对 𝑖, 𝑗 ∈
{1,2, ⋯ , 𝑛},假设 𝑎𝑖𝑗 是 𝑖 对 𝑗 的交互分值。对 𝐴 中的每一行归一化,即定义:
𝑗=1
(1)对任意 𝑖,𝑎𝑖 = ∑𝑛
(2)对任意 𝑖, 𝑗,定义 𝑏
𝑎𝑖𝑗 ;
= 𝑎𝑖𝑗,则 𝐵 = (𝑏
) 是一个不可约非
𝑖𝑗
𝑎𝑖
𝑖𝑗
负矩阵,而且 𝐵 的每一行所有数值相加为 1。非负矩阵有一个基本定理:
定理 10.1(Perron Forbenius)如果 𝐵 ≥ 0 是不可约矩阵,而且
𝐵 的每一行之和为 1,那么:
(1) 𝐵 的最大特征值为 1;
(2) 𝐵 的最大特征值 1 存在唯一的左特征向量;
(3) 𝐵 最大特征值 1 的唯一左特征向量是一个概率分布,即存在唯一的向量 𝜋𝑇 = (𝜋1, 𝜋2, ⋯ , 𝜋𝑛),满足:
①每一个 𝜋𝑖 > 0,
② 𝜋𝑇𝐵 = 𝜋𝑇,
∑③
𝑛
𝑖=1
𝜋𝑖 = 1。
定义 10.3(稳定分布)假设 𝐴 ≥ 0 是不可约矩阵,令 𝐵 是 𝐴
的归一化矩阵,使得 𝐵 的每一行相加为 1,令 𝜋𝑇 = (𝜋1, 𝜋2, ⋯ , 𝜋𝑛)是 𝐵 的 最大特征值的唯 一的左特征向量 。 我们称 𝜋𝑇 = (𝜋1, 𝜋2, ⋯ , 𝜋𝑛) 是 𝐴 的稳定分布。