假设 $n \times n$ 矩阵 $A$ 有 $n$ 线性无关的特征向量$x_{1}, \ldots, x_{n}$ ，将这n个特征向量组成特征向量矩阵 $S$. 那么 $S^{-1} A S$ 是特征值矩 $\Lambda$。

$S^{-1} A S=\Lambda=\left[\begin{array}{lll}\lambda_{1} & \\ & \ddots \\ & & \lambda_{n}\end{array}\right]$
证明：

$A S=A\left[\begin{array}{lll}x_{1} & \cdots & x_{n}\end{array}\right]=\left[\begin{array}{lll}\lambda_{1} x_{1} & \cdots & \lambda_{n} x_{n}\end{array}\right]$
$S\Lambda=\left[\begin{array}{lll}x_{1} & \cdots & x_{n}\end{array}\right]\left[\begin{array}{lll}\lambda_{1} & \\ & \ddots \\ & & \lambda_{n}\end{array}\right]=\left[\begin{array}{lll}\lambda_{1} x_{1} & \cdots & \lambda_{n} x_{n}\end{array}\right]$
因此 $AS=S\Lambda$,即 $S^{-1} A S=\Lambda$
附：矩阵（方阵）能完全对角化的条件是n个线性无关的特征向量。若矩阵有n个完全不同的特征值，则一定可以对角化。

一、特殊矩阵（方阵）

方阵：是指行数与列数相同的矩阵
	
一些常用的特殊方阵如下：
	
对角矩阵：M是一个对角矩阵，当且仅当i!=l时，M(i,j)=0
		
三对角矩阵：M是一个三对角矩阵，当且仅当|i-j|>1时，M(i,j)=0
		
下三角矩阵：M是一个下三角矩阵，当且仅当i<j时，M(i,j)=0
		
上三角矩阵：M是一个上三角矩阵，当且仅当i>j时，M(i,j)=0
		
对称矩阵：M是一个对称矩阵，当且仅当对于所有的j和j，M(i,j)=M(j,i)
	




二、特殊矩阵（方阵）在实际中的应用


应用①

佛罗里达州的6个城市Gainsville、Jacksonville、Miami、Orlando、Tallaha-ssee和Tampa
	
按照这个顺序，依次从1~6编号。任意两个城市之间的距离用一个6*6的矩阵distance表示。矩阵的第i行和第i列代表第i个城市。distance(i,j)代表城市i和城市j之间的距离
	
下图给出了相应的矩阵，因为对于所有的i和j有distance(i,j)=distance(j,i)，所以这是一个对称矩阵




应用②






三、对角矩阵

对角矩阵：M是一个对角矩阵，当且仅当i!=l时，M(i,j)=0



编码实现：

一个rows*rows的对角矩阵D可以表示为一个二维数组element[rows][rows]，其中element[i-1][j-1]=D(i,i)。这种表示法需要rows*rows个类型为T的数据空间
	
然后对角矩阵最多只有rows个非0元素，因此可以用一位数组element[rows]来表示，其中element[i-1]=D(i,i)，所有未在一维数组中出现的矩阵元素均为0
异常类定义

class illegalParameterValue
{
	string message;
public:
	illegalParameterValue(const char *theMessage ="Illegal Parameter Value"):message(theMessage) {}
	const char *what() {
		return message.c_str();
	}
};

class matrixIndexOutOfBounds
{
public:
	matrixIndexOutOfBounds(string theMessage = "Matrix index out of bounds") :message(theMessage){}
	const char *what() {
		return message.c_str();
	}
private:
	string message;
};

类定义

template<typename T>
class diagonalMatrix
{
public:
	diagonalMatrix(int theN = 10);
	~diagonalMatrix();
	void set(int i, int j, T value);
	T get(int i, int j)const;
	void output(ostream& out) const;
private:
	T *element;  //存放矩阵的数组
	int n;  //矩阵维度
};

类成员实现

构造函数时间复杂度：当T时内部数据类型时为O(1)，当T为用户定义类型时为O(rows)
	
get、set的时间复杂度：Θ(1)
template<typename T>
diagonalMatrix<T>::diagonalMatrix(int theN = 10)
{
	if (theN < 1) {
		throw illegalParameterValue("Parameter mu be >=1");
	}

	element = new T[theN];
	n = theN;
}

template<typename T>
diagonalMatrix<T>::~diagonalMatrix()
{
	if (element) {
		delete[] element;
		element = nullptr;
	}
}

template<typename T>
void diagonalMatrix<T>::set(int i, int j, T value)
{
	if ((i<1) || (j<1) || (i>n) || (j>n)) {
		throw matrixIndexOutOfBounds();
	}

	if (i == j) {
		element[i] = value;
	}
	else {
		if (value != 0) {
			throw illegalParameterValue("nondiagonal elements must be zero");
		}
	}
}

template<typename T>
T diagonalMatrix<T>::get(int i, int j)const
{
	if ((i<1) || (j<1) || (i>n) || (j>n)) {
		throw matrixIndexOutOfBounds();
	}

	if (i == j)
		return element[i];
	else
		return 0;
}

template<typename T>
void diagonalMatrix<T>::output(ostream& out) const
{
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; j++) {
			if (i == j) {
				out << element[i]<<" ";
				continue;
			}
			out << "0 ";
		}
		out << endl;
	}
}

演示案例

int main()
{
	diagonalMatrix<int> *matrix = new diagonalMatrix<int>(3);

	matrix->set(1,1,1);
	matrix->set(2, 2, 2);
	matrix->set(3, 3, 3);

	cout << "matrix[1,1]="<< matrix->get(1, 1) <<endl;
	cout << "matrix[2,2]=" << matrix->get(2, 2) << endl;
	cout << "matrix[3,3]=" << matrix->get(3, 3) << endl;

	matrix->output(cout);

	return 0;
}




四、三对角矩阵

三对角矩阵：M是一个三对角矩阵，当且仅当|i-j|>1时，M(i,j)=0


非0元素排列在如下三条对角线上：

	
①主对角线：i=j
		
②主对角线之下的对角线（称为低对角线）：i=j+1
		
③主对角线之上的对角线（称为高对角线）：i=j-1
	

编码实现：

三条对角线上的元素总数为3*rows-2。可以用一个容量3*rows-2的一维数组element来描述三对角矩阵
	
以下图这个三对角矩阵为例：
	
如果逐行映射：则element[0-9]={2,1,3,1,3,5,7,9,0}
		
如果逐列映射：则element[0-9]={2,3,1,1,5,3,2,9,7,0}
		
如果从低对角线开始逐条对角线映射：则element[0-9]={3,5,9,2,1,2,0,1,3,7}
	


每一种映射方式，get和set方法的代码都不同，下面我们假设为逐条对角线映射
异常类定义

class illegalParameterValue
{
	string message;
public:
	illegalParameterValue(const char *theMessage ="Illegal Parameter Value"):message(theMessage) {}
	const char *what() {
		return message.c_str();
	}
};

class matrixIndexOutOfBounds
{
public:
	matrixIndexOutOfBounds(string theMessage = "Matrix index out of bounds") :message(theMessage){}
	const char *what() {
		return message.c_str();
	}
private:
	string message;
};

类定义 

template<typename T>
class tridiagonalMatrix
{
public:
	tridiagonalMatrix(int theN = 10);
	~tridiagonalMatrix();
	T get(int i,int j)const;
	void set(int i, int j, T value);
	void output(ostream& out) const;
private:
	T *element;  //存放矩阵的数组
	int n; //矩阵维数
};

类成员实现

template<typename T>
tridiagonalMatrix<T>::tridiagonalMatrix(int theN = 10)
{
	if (theN < 1) {
		throw illegalParameterValue("Parameter mu be >=1");
	}

	element = new T[3*theN-2];
	n = theN;
}

template<typename T>
tridiagonalMatrix<T>::~tridiagonalMatrix()
{
	if (element) {
		delete[] element;
		element = nullptr;
	}
}

template<typename T>
 T tridiagonalMatrix<T>::get(int i, int j)const
{
	if ((i<1) || (j<1) || (i>n) || (j>n)) {
		throw matrixIndexOutOfBounds();
	}

	switch (i-j)
	{
	case 1: //下对角线
		return element[i - 2];
	case 0: //主对角线
		return element[n + i - 2];
	case -1: //上对角线
		return element[2 * n + i - 2];
	default:
		return 0;
	}
}

template<typename T>
void tridiagonalMatrix<T>::set(int i, int j, T value)
{
	if ((i<1) || (j<1) || (i>n) || (j>n)) {
		throw matrixIndexOutOfBounds();
	}

	switch(i - j)
	{
	case 1: //下对角线
		element[i - 2] = value;
		break;
	case 0: //主对角线
		element[n + i - 2] = value;
		break;
	case -1: //上对角线
		element[2 * n + i - 2] = value;
		break;
	default:
		if (value != 0) {
			throw illegalParameterValue("nondiagonal elements must be zero");
		}
		break;
	}
}

template<typename T>
void tridiagonalMatrix<T>::output(ostream& out) const
{
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			switch (i - j)
			{
			case 1: //下对角线
				out << element[i - 2] << " ";
				continue;
			case 0: //主对角线
				out << element[n + i - 2] << " ";
				continue;
			case -1: //上对角线
				out << element[2 * n + i - 2]<<" ";
				continue;
			default:
				out << "0 ";
				continue;
			}
		}
		out << endl;
	}
}

演示效果

int main()
{
	tridiagonalMatrix<int> *matrix = new tridiagonalMatrix<int>(4);
	matrix->set(1, 1, 2);
	matrix->set(1, 2, 1);
	matrix->set(2, 1, 3);
	matrix->set(2, 2, 1);
	matrix->set(2, 3, 3);
	matrix->set(3, 2, 5);
	matrix->set(3, 3, 2);
	matrix->set(3, 4, 7);
	matrix->set(4, 3, 9);
	matrix->set(4, 4, 0);

	matrix->output(cout);
	return 0;
}




五、三角矩阵

下三角矩阵：M是一个下三角矩阵，当且仅当i<j时，M(i,j)=0
	
上三角矩阵：M是一个上三角矩阵，当且仅当i>j时，M(i,j)=0



编码实现：

在一个n行的下三角矩阵中（见下图），非0区域的第一行有1个元素，第二行有2个元素，......，第n行有n个元素
	
在一个n行的上三角矩阵中（见下图），非0区域的第一行有n个元素，第二行有n-1个元素，......，第n行有1个元素


总结：下三角矩阵或上三角矩阵中非0区域共有非0元素：n(n+1)/2。一个三角矩阵可以用一个大小为n(n+1)/2的一维数组来表示
	
以下面的下三角矩阵为例：
	
按行映射：element[0-9]={2,5,1,0,3,1,4,2,7,0}
		
按列映射：element[0-9]={2,5,0,4,1,3,2,1,7,0}
	


下三角矩阵的元素L(i,j)：

	
如果i<j，则L(i,j)=0
		
如果i>=j，则L(i,j)位于非0区域。如果按行映射，在元素L(i,j)（i>=j）之前分别有个元素位于第1行至第i-1行的非0区域和j-1个元素位于第i行的非0区域拒，共有个
	
异常类定义

class illegalParameterValue
{
	string message;
public:
	illegalParameterValue(const char *theMessage ="Illegal Parameter Value"):message(theMessage) {}
	const char *what() {
		return message.c_str();
	}
};

class matrixIndexOutOfBounds
{
public:
	matrixIndexOutOfBounds(string theMessage = "Matrix index out of bounds") :message(theMessage){}
	const char *what() {
		return message.c_str();
	}
private:
	string message;
};

类定义 

template<typename T>
class lowerTriangularMatrix
{
public:
	lowerTriangularMatrix(int theN = 10);
	~lowerTriangularMatrix();
	void set(int i, int j, T value);
	T get(int i, int j)const;
	void output(ostream& out) const;
private:
	T *element;  //存放矩阵的数组
	int n;  //矩阵维度
};

类成员实现

template<typename T>
lowerTriangularMatrix<T>::lowerTriangularMatrix(int theN = 10)
{
	if (theN < 1) {
		throw illegalParameterValue("Parameter mu be >=1");
	}

	element = new T[theN*(theN + 1) / 2];
	n = theN;
}

template<typename T>
lowerTriangularMatrix<T>::~lowerTriangularMatrix()
{
	if (element) {
		delete[] element;
		element = nullptr;
	}
}

template<typename T>
void lowerTriangularMatrix<T>::set(int i, int j, T value)
{
	if ((i<1) || (j<1) || (i>n) || (j>n)) {
		throw matrixIndexOutOfBounds();
	}

	if (i >= j) {
		element[i*(i - 1) / 2 + j - 1] = value;
	}
	else {
		if (value != 0) {
			throw illegalParameterValue("nondiagonal elements must be zero");
		}
	}
}

template<typename T>
T lowerTriangularMatrix<T>::get(int i, int j)const
{
	if ((i<1) || (j<1) || (i>n) || (j>n)) {
		throw matrixIndexOutOfBounds();
	}

	if (i >= j)
		return element[i*(i - 1) / 2 + j - 1];
	else
		return 0;
}

template<typename T>
void lowerTriangularMatrix<T>::output(ostream& out) const
{
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; j++) {
			if (i >= j) {
				out << element[i*(i - 1) / 2 + j - 1] << " ";
				continue;
			}
			out << "0 ";
		}
		out << endl;
	}
}

演示效果

int main()
{
	lowerTriangularMatrix<int> *matrix = new lowerTriangularMatrix<int>(4);
	matrix->set(1, 1, 2);
	matrix->set(2, 1, 5);
	matrix->set(2, 2, 1);
	matrix->set(3, 1, 0);
	matrix->set(3, 2, 3);
	matrix->set(3, 3, 1);
	matrix->set(4, 1, 4);
	matrix->set(4, 2, 2);
	matrix->set(4, 3, 7);
	matrix->set(4, 4, 0);

	matrix->output(cout);

	return 0;
}




六、对称矩阵

对称矩阵：M是一个对称矩阵，当且仅当对于所有的j和j，M(i,j)=M(j,i)


编码实现：一个n*n的对称矩阵，可以视为下三角或上三角矩阵，用三角矩阵的表示方法，用一个大小为n(n+1)/2的一维数组来表示。未存储的元素可以用存储的元素来计算
七、总结

代码下载见：https://download.csdn.net/download/qq_41453285/12007285

对角矩阵的压缩存储
什么是对角矩阵
矩阵的压缩
1，当带宽b=1时
2，当b不等于1.且b小于n/2

什么是对角矩阵


定义

若一个n阶方阵A满足其所有非零元素都集中在以主对角为中心的带状区域中，则称其为n阶对角矩阵(diagonal matrix)。


图片解释




矩阵的压缩
1，当带宽b=1时
只有一条带子，像上面那个图一样，第一行（列）最后一行（列）都只有两个元素，

按照行存储   也就是一行一行的存储
a[i][j]=2+(i-1)*3+(j-(i-b))
a[i][j]=2i+j

2，当b不等于1.且b小于n/2

行排序

a[i][j]=1+b+(i-1)*(b+2)+ (j-(i-b))=k
列排序

a[i][j]=1+b+(j-1)*(b+2)+(i-(j-b))=k

特殊矩阵——三对角矩阵(Tridiagonal Matrix)

注：压缩存储的矩阵可以分为特殊矩阵和稀疏矩阵。对于那些具有相同元素或零元素在矩阵中分布具有一定规律的矩阵，被称之为特殊矩阵。对于那些零元素数据远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称之为稀疏矩阵。



1. 三对角矩阵的概念

三对角矩阵就是对角线、邻近对角线的上下次对角线上有元素，其他位置均为0的矩阵。
三对角矩阵是一种特殊的上Hessenberg矩阵(这个就是上三角矩阵加上下三角部分的第一条次对角线有元素，其他都为0元素)。
2. 三对角矩阵的特性

设一个n*n的方阵A，对于矩阵A中的任一元素aij，当|i-j|>1时，有aij=0(0≤i≤n−1，0≤j≤n−1)时，矩阵A为三对角矩阵。
三对角矩阵中除主对角线及在主对角线上下最邻近的两条对角线上的元素外，所有其他元素均为0。
3. 三对角矩阵的压缩存储

可以利用三对角矩阵的上述特性，只存储主对角线及其上、下两侧次对角线上的元素，其他的零元素一律不存储。对一个n*n的三对角方阵A，元素总数有n2个，而其中非零的元素共有3*n-2个。因此，存储三对角矩阵时最多只需存储3*n-2个元素。 

可以仿照对称矩阵的压缩存储，可用一维数组B存储三对角矩阵A(这要区分两种存储方式：行优先方式和列优先方式)。   
(1)行优先方式存储 

(2)列优先方式存储 

4. 三对角矩阵的实现

文件：TridiagonalMatrix.h


#include <iostream>


using namespace std;

//压缩存储后，存储对称方阵时最多只需存储n*(n+1)/2个元素

#define GetTotalLen(n) 3 * n - 2                


//按行优先方式存放三对角矩阵，矩阵元素下标对应的一维数组的下标

#define GetIndexRow(i, j) 2 * i + j 


//按列优先方式存放三对角矩阵，矩阵元素下标对应的一维数组的下标

#define GetIndexCol(i, j) 2 * j + i



class TridiagonalMatrix
{
public:
    TridiagonalMatrix(int order);

    ~TridiagonalMatrix();

public:
    void create();                      //创建矩阵

    void destroy();                     //销毁矩阵

    void transpos();                    //矩阵转置

    int get_order();                    //获取矩阵阶数

    int* compressed_storage_row();      //压缩存储特殊矩阵——三对角矩阵，按行优先方式存放

    int* compressed_storage_col();      //压缩存储特殊矩阵——三对角矩阵，按列优先方式存放

    bool is_tridiagonal();              //判断矩阵是否为三对角矩阵

public:
    friend ostream& operator<<(ostream& os, TridiagonalMatrix& m);    //输出矩阵

private:
    int _order;
    int **_matrix;
};
文件：TridiagonalMatrix.cpp


#include "TridiagonalMatrix.h"


#include <math.h>


TridiagonalMatrix::TridiagonalMatrix(int order)
: _order(order), _matrix(new int*[order])
{
    create();
}

TridiagonalMatrix::~TridiagonalMatrix()
{
    destroy();
}

void TridiagonalMatrix::create()
{
    for (int i = 0; i < _order; i++)
    {
        _matrix[i] = new int[_order];
        for (int j = 0; j < _order; j++)
        {
            if (abs(i-j) > 1)
            {
                _matrix[i][j] = 0;
            }
            else
            {
                _matrix[i][j] = 1;
            }
        }
    }
}

void TridiagonalMatrix::destroy()
{
    for (int i = 0; i < _order; i++)
    {
        delete[] _matrix[i];
    }
    delete[] _matrix;
    _matrix = NULL;
}

void TridiagonalMatrix::transpos()
{
    int temp = 0;
    for (int i = 0; i < _order; i++)
    {
        for (int j = 0; j < _order; j++)
        {
            temp = _matrix[i][j];
            _matrix[i][j] = _matrix[j][i];
            _matrix[j][i] = temp;
        }
    }
}


int TridiagonalMatrix::get_order()
{
    return _order;
}

int* TridiagonalMatrix::compressed_storage_row()
{
    int index = 0;
    int total_count = GetTotalLen(_order);
    int *a = new int[total_count];
    for (int i = 0; i < _order; i++)
    {
        for (int j = 0; j < _order; j++)
        {
            if (abs(i-j) <= 1)
            {
                index = GetIndexRow(i, j);
                a[index] = _matrix[i][j];
            }
        }   
    }
    return a;
}

int* TridiagonalMatrix::compressed_storage_col()
{
    int index = 0;
    int total_count = GetTotalLen(_order);
    int *a = new int[total_count];
    for (int j = 0; j < _order; j++)
    {
        for (int i = 0; i < _order; i++)
        {
            if (abs(i - j) <= 1)
            {
                index = GetIndexCol(i, j);
                a[index] = _matrix[i][j];
            }
        }
    }
    return a;
}

bool TridiagonalMatrix::is_tridiagonal()
{
    for (int i = 0; i < _order; i++)
    {
        for (int j = 0; j < _order; j++)
        {
            if ((abs(i-j) > 1) && (_matrix[i][j] != 0))
            {
                return false;
            }
        }
    }
    return true;
}

ostream& operator<<(ostream& os, TridiagonalMatrix& m)
{
    os << "三对角矩阵：" << endl;
    for (int i = 0; i < m._order; i++)
    {
        for (int j = 0; j < m._order; j++)
        {
            os << m._matrix[i][j] << " ";
        }
        os << endl;
    }
    return os;
}
文件：main.cpp


#include "TridiagonalMatrix.h"


int main()
{
    int n = 0;
    cout << "请输入三对角矩阵的阶数，n = ";
    cin >> n;

    TridiagonalMatrix matrix(n);
    if (true == matrix.is_tridiagonal())
    {
        cout << "$ 输出三对角矩阵：" << endl;
        cout << matrix;//或operator<<(cout, matrix);
    }

    matrix.transpos();
    if (true == matrix.is_tridiagonal())
    {
        cout << "$ 输出转置后的三对角矩阵：" << endl;
        cout << matrix;//或operator<<(cout, matrix);
    }

    cout << "\n$ 输出压缩存储后的一维数组(按行优先方式存放)：" << endl;
    int *arrayr = matrix.compressed_storage_row();
    for (int i = 0; i < GetTotalLen(matrix.get_order()); i++)
    {
        cout << arrayr[i] << " ";
    }
    cout << endl;
    delete[] arrayr;

    cout << "\n$ 输出压缩存储后的一维数组(按列优先方式存放)：" << endl;
    int *arrayc = matrix.compressed_storage_col();
    for (int i = 0; i < GetTotalLen(matrix.get_order()); i++)
    {
        cout << arrayc[i] << " ";
    }
    cout << endl;
    delete[] arrayc;

    system("pause");
    return 0;
}
参考文献： 

[1]《数据结构(用面向对象方法与C++语言描述)(第2版)》殷人昆——第四章  

[2] 百度搜索关键字：三对角线矩阵、多对角线矩阵