Abstract
In this chapter, linear algebra is employed for the study of symmetry, followed by graph-theoretical interpretations. The application of the methods presented in this chapter is not limited to geometric symmetry. Thus, the symmetry studied here can more appropriately be considered as topological symmetry. The methods considered in this chapter can be considered as special techniques for transforming the matrices into block triangular forms. These forms allow good saving of computation effort for many important problems such as computing determinants, eigenvalue problems and solution of linear system of equations. For each of these tasks with dimension N, the computing cost grows approximately with N3. Therefore, reducing, for example, the dimension to N/2, the effort decreases eight times which is a great advantage.
Access provided by Autonomous University of Puebla. Download chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
4.1 Introduction
In this chapter, linear algebra is employed for the study of symmetry, followed by graph-theoretical interpretations. The application of the methods presented in this chapter is not limited to geometric symmetry. Thus, the symmetry studied here can more appropriately be considered as topological symmetry. The methods considered in this chapter can be considered as special techniques for transforming the matrices into block triangular forms. These forms allow good saving of computation effort for many important problems such as computing determinants, eigenvalue problems and solution of linear system of equations. For each of these tasks with dimension N, the computing cost grows approximately with N3. Therefore, reducing, for example, the dimension to N/2, the effort decreases eight times which is a great advantage.
Here different canonical forms are presented. Methods are developed for decomposing and healing of the graph models associated with these forms for efficient calculation of the eigenvalues of matrices associated with these forms [1–5]. The formation of divisors and co-divisors, using a graph-theoretical approach, is developed by Rempel and Schwolow [6] and well described in reference [7]. Here, only symmetric forms are presented, since simple graph-theoretical concepts are sufficient for their formation. Two important forms known as tri-diagonal and penta-diagonal forms are also presented, and methods are provided for their decomposition. It is shown that different canonical forms can be derived from the block tri-diagonal form [8, 9].
4.2 Decomposition of Matrices to Special Forms
In this section, a 2N × 2N symmetric matrix M is considered with all entries being real. For four canonical forms, the eigenvalues of M are obtained using the properties of its submatrices.
4.2.1 Canonical Form I
In this case, matrix M has the following pattern:
Considering the set of eigenvalues of the submatrix A as \( \{\uplambda \mathbf{A}\} \), the set of eigenvalues of M can be obtained as follows:
where the sign \( \overline{\cup} \) is used for the collection of the eigenvalues of the submatrices and not necessarily their union.
Since det M = det A × det A, the proof becomes evident. Here ‘det’ stands for the determinant.
Form I can be generalised to a decomposed form with diagonal submatrices A 1, A 2, A 3, …, A p of different dimensions, and the eigenvalues can be calculated as follows:
The proof follows from the fact that det M = det A 1 × det A 2 × det A 3 × … × det A p.
Example 4.1
Consider the matrix M as follows:
with \( \mathbf{A}=\left[ {\begin{array}{lll} 1 & 2 \\3 & 4 \\\end{array}} \right] \).
Since {λA} = {−0.3723, 5.3723}, therefore {λM} = {−0.3723, 5.3723, −0.3723, 5.3723}.
4.2.2 Canonical Form II
For this case, matrix M can be decomposed into the following form:
The eigenvalues of M can be calculated as follows:
C and D are called condensed submatrices of M.
Proof
In block form, addition of the second column of the matrix M to the first column and reducing the first row from the second row results in
where
and
and the proof is complete.
Example 4.2
Consider the matrix M as follows:
This matrix has the pattern of Form II and is decomposed according to Eq. 4.4, leading to
Matrices C and D are formed using Eq. 4.5 as
For these matrices, the eigenvalues are
hence,
4.2.3 Canonical Form III
This form has a Form II submatrix augmented by some rows and columns as shown in the following:
where M is a (2N + k) × (2N + k) matrix, with a 2N × 2N submatrix with the pattern of Form II, and k augmented columns and rows. The entries of the augmented columns at the top right-hand side are L1i, L2i,…, LNi (i = 1,…,k) and then repeated again, and all the entries of M are real numbers.
Now D is obtained as D = A − B, and E is constructed as the following:
D is an N × N matrix and E is an (N + k) × (N + k) matrix. The set of eigenvalues for M is obtained as follows:
Proof
Similar to Form II, M can be factored by rows and columns permutation. In this case, first the augmented rows and columns are transformed into the central part of the matrix. The last column (in block form) is added to the first column, followed by reducing the first row from the last row.
that is, the matrix is now in a factored form.
where D and E are constructed as follows:
and
Example 4.3
Consider a matrix M as follows:
Condensed submatrices are calculated using Eq. 4.15 as follows:
and
Eigenvalues for D and E are calculated as follows:
Therefore, the eigenvalues of M are obtained:
4.2.4 Transformation of Form III into Form II
In this section, it is shown that the canonical Form III can be obtained from the canonical Form II, Ref. [10]. In order to show this property, the following results are first considered:
Let a 2N × 2N matrix L be augmented by an arbitrary row and a column with all zero entries, as follows:
The matrix C has in its (2N + 1)th column all zero entries, and the eigenvalues of C and L are identical, with the exception of an additional zero eigenvalue for C. This can be proved as follows:
The first 2N rows of C are multiplied by k1, k2, …, k2N, respectively, and the sum is equated to zero. Since any multiple of the last column will be zero, therefore the following equations are obtained:
If L is invertible (i.e. if det (L) ≠ 0), then K = −L −1 X and k1, k2, …, k2N can be found and the last row of C becomes zero. However, if det (L) = 0, then there are many sets of ki which put the last row of C into zero. Therefore, one can conclude that there is always at least one transformation that makes the last row of C as zero.
If the kth row of a matrix is multiplied in m and the kth column is divided by m, the eigenvalues of this matrix stay unchanged. The reason is that the magnitude of the diagonal entry stays constant, and if it is expanded with respect to a row and column, the determinant of the submatrices stays unaltered.
Algorithm
Add a zero column together with an arbitrary row with zero entry in the second column as shown in the following:
Add half of the 4th column to column 2, and add half of 4th row to row 2. Now interchange column 2 with column 4. These operations are shown in the following:
Column 4 is multiplied by 2 and row 4 is multiplied by 1/2, resulting in
where
Column 2 is multiplied by 1/2, and the second row is multiplied by 2, resulting in E.
The right-hand matrix M − N in Eq. 4.20 has the same eigenvalues as those of A − B with exception of having 2N extra zeros. E and D are the same matrices obtained for Form III in the previous section.
4.2.5 Form IV Symmetry
Definition
Consider the following 6 × 6 matrix in a tri-diagonal form:
The entries of M have the following properties:
-
1.
Each row-sum of this matrix is equal to zero and the row-sum of non-diagonal entries has the same value as its diagonal entry with reverse sign.
-
2.
Matrix M has a central core in the following form:
The core C consists of two parts in Form II, with Q showing the type of the link between these two parts.
Matrix M is obtained by the addition of two rows and two columns to the beginning and end of C.
The characteristic polynomial of M can be expressed as follows:
-
The first term of this equation can be considered as the characteristic equation of the following matrix;
$$ {{\mathbf{e}}_1}=\left[ {\begin{array}{lll} \mathrm{{s}-{\rm h}} & {{\rm h}-\mathrm{s}} \\{{\rm h}-\mathrm{s}} & \mathrm{{s}-{\rm h}} \\\end{array}} \right]\Rightarrow \uplambda {{\mathbf{e}}_1}=\{0,-2\mathrm{h}+2\mathrm{s}\}; $$(4.25)e 1 is a matrix of Form II.
-
The second term of Eq. 4.24 can be taken as the characteristic equation of the following matrix:
$$ {{\mathbf{e}}_2}=\left[ {\begin{array}{lll} \mathrm{{s}+{\rm h}} & {-\mathrm{s}} \\\mathrm{s} & \mathrm{{s}-{\rm h}} \\\end{array}} \right]\Rightarrow \uplambda {{\mathbf{e}}_2}=\left\{ \mathrm{{s}+\sqrt{{{\mathrm{{s}}^2}+{{{\rm h}}^2}-{\rm sh}}},\mathrm{s}-\sqrt{{{\mathrm{{s}}^2}+{{{\rm h}}^2}-\mathrm{s}\mathrm{h}}}} \right\}. $$(4.26) -
The third part of Eq. 4.24 is treated as the characteristic equation of
$$ {{\mathbf{e}}_3}=\left[ {\begin{array}{lll} {2\mathrm{s}} & {3{\rm h}} \\{{\rm h}-\mathrm{s}} & 0 \\\end{array}} \right]\Rightarrow \uplambda {{\mathbf{e}}_3}=\left\{ \mathrm{{s}+\sqrt{{{\mathrm{{s}}^2}-3\mathrm{sh}+3{\mathrm{{h}}^2}}},\mathrm{s}-\sqrt{{{\mathrm{{s}}^2}-3\mathrm{sh}+3{\mathrm{{h}}^2}}}} \right\}. $$(4.27)
Rearranging the entries of an arbitrary matrix M, one may find one or more submatrices such that the eigenvalues of these submatrices are among the eigenvalues of M. Then M is called a reflective matrix, and the submatrices with the above properties are called the principal submatrices of M.
Now we want to know when M is a reflective matrix and which submatrices of M are principal. Suppose
be a principal submatrix of M. For SM we have
In order to relate the eigenvalues of SM to those of e 3, the polynomials of SM and e 3 are equated as
resulting in
Thus, for s = 2h and s = h, the matrix M becomes reflective, and SM in Eq. 4.28 becomes its principal submatrix.
For s = 2h,
and
It is easy to show that for s = 2h,
and similarly
Therefore
Hence, for s = 2h, the matrix M becomes a well-structured reflective matrix.
4.2.6 Method for the Formation of e 1 and e 2 Matrices
The matrix M of Eq. 4.22 can be considered as two Form III matrices connected to each other by a submatrix Q as follows:
The upper-left part being a Form III matrix having the following condensed matrix:
This matrix has a Form II core as follows:
Hence, using Eq. 4.7, its factorisation leads to
The lower-right part of M in Eq. 4.22 has Form III symmetry as
with a condensed matrix:
The submatrices e 1 and e 2 are called operative submatrices of M.
Example 4.4
Consider a 6×6 matrix M as follows:
For this matrix, s = 5 and h = 2, and since s ≠ h and s ≠ 2h, therefore M cannot be a reflective matrix.
The eigenvalues of M are as follows:
The operative submatrices are constructed as follows:
Therefore,
Now if we select s = 2h with h = 1, then a reflective matrix will be formed as follows:
with
The submatrix e 3 is a principal submatrix of M, since the eigenvalues of e 2 are reflected in those of M. As the eigenvalues of e 3 have no common overlap with those of e 1 and e 2, hence, M is a well-structured reflective matrix.
The submatrices and their eigenvalues are calculated as follows:
4.3 Generalization of Form IV to Higher-Order Matrices
In order to maintain the properties of the previous matrices, the row-sum of non-diagonal entries should be the same as the diagonal entry of the considered row with reverse sign.
Consider an N × N block symmetric matrix M g for which the cores E 1, E 2 and E 3 contain submatrices S and H in place of the entries s and h. Therefore, M g can be written as follows:
Since [H − S]t = [H − S], therefore S 6 × 6 and H 6 × 6 are both symmetric. For this matrix E 1, E 2 and E 3 are calculated as follows:
Example 4.5
The following 12 × 12 matrix has the required properties.
Considering the partitioning with 2 × 2 submatrices, S and H are as follows:
Now the cores E 1, E 2 and E 3 are formed as follows:
E 1 itself has a Form II symmetry, and using Eq. 4.15 it is decomposed as follows:
Therefore,
The matrices E 2 and E 3 are constructed by substituting S and H in Eq. 4.38. The calculation for the eigenvalues of the submatrices in a similar manner leads to
Thus,
Remark
Consider the central core of M g as a principal submatrix M gP, that is,
then the eigenvalues will be
Therefore, M g is a well-structured reflective matrix.
4.4 Special Pattern Form IV Matrices
Here, the conditions are derived for having well-structured reflective matrices. Consider the following matrix:
The difference between this matrix and that of Eq. 4.22 is that in M s the row-sum for rows is s − 2h and not zero. The characteristic polynomial of M s is as follows:
The first term can be taken as the polynomial for the following e 1 matrix:
The second part of the polynomial corresponds to
This matrix is a principal submatrix of M s, since its eigenvalues are reflected in those of M s. It has Form II symmetry and the eigenvalues can be obtained using this property.
The third part belongs to
Therefore,
This special case can also be generalised to matrices of higher dimensions, by considering submatrices S and H in place of the entries s and h.
For this form, one can easily identify the principal submatrix positioned at the central part of the matrix. The submatrices S and H can immediately be formed and used in the formation of E 2 and E 3 matrices.
Example 4.6
Consider a 12 × 12 matrix as follows, which has the properties of special Form IV matrices.
The principal submatrix can easily be identified as
and we have
E 1 and E 2 and the corresponding eigenvalues can then easily be calculated as follows:
Similarly
Leading to
4.5 Eig[M] Operator
For a matrix M, Eig[M] is defined as an operator which acts on M and results its eigenvalues. For example, for an N × N matrix M we have
For the factors E 1, E 2 and E 3, we had
The most interesting property of Form IV is that if S and H submatrices are replaced by s and h, then the operator ‘Eig’ will be as follows:
This simplifies the computation, since once S and H are formed, all the eigenvalues of M can be obtained as follows:
and there is no need for explicit formation of E 1, E 2 and E 3. The application is presented in the following section.
4.6 Laplacian Matrices for Different Forms
The Laplacian matrix L(S) is an important matrix associated with a graph S. The list of eigenvalues together with their multiplicities of L(S) is known as the spectrum of S. There are interesting relationships between the properties of a graph and the Laplacian spectrum. Since a graph is the underlying model of a vibrating structure or a system, therefore eigenvalues of graphs are of great importance in their study.
The Laplacian L(S) = [lij]N × N of a weighted graph S is an N × N matrix defined as follows:
where N is the number of vertices of the graph and
When the weights of members are considered as one, then D(S) and A(S) become the degree matrix and adjacency matrix of S, respectively.
4.6.1 Symmetry and Laplacian of Graphs
In this section, M is taken as the Laplacian of S, and for different forms of M, the corresponding graphs are introduced. This correspondence provides an efficient means for calculating the eigenvalues of the Laplacian of graphs.
Consider a symmetric graph S with an axis of symmetry. The following cases may arise:
Symmetry of Form I: The axis of symmetry does not pass through members and nodes. In this case, S is a disjoint graph and its components S1 and S2 are isomorphic subgraphs, Fig. 4.1. In order to have the Laplacian matrix in Form I, the nodes of S1 are numbered first as 1, 2, …, N/2, followed by the labelling of the nodes of S2 as N/2 + 1, N/2 + 2,…,N, such that for a typical node I in S1, the corresponding symmetric counterpart in S2 is labelled as I + N/2.
Symmetry of Form I
Symmetry of Form II: The axis of symmetry passes through members, and the graph S has an even number of nodes. The members cut by the axis of symmetry are called link members, and their end nodes are taken as linked nodes, Fig. 4.2. Link members connect the two isomorphic subgraphs S1 and S2 to each other. For this case, two different types of connections can be considered, as illustrated in Fig. 4.2a, b. The first one is a direct connection and the second is called a cross-connection.
Symmetry of Form II. (a) A direct connection. (b) A cross-connection
In a direct connection, a typical node I in S1 is connected to the node labelled as I + N/2 in S2 by a link member. In cross-connection, a typical pair of nodes I and J in S1 is connected to J + N/2 and I + N/2, respectively. A combination of the direct and cross-connection is also possible.
For some graphs, the axis of symmetry may pass through an even number of nodes, as illustrated in Fig. 4.3a. Then, one may still consider the graph as Form II by altering the axis of symmetry, as shown in Fig. 4.3b, while maintaining the topological symmetry of the model.
Symmetry of Form II with axis passing through nodes. (a) The axis of symmetry. (b) Altering the axis of symmetry
Symmetry of Form III: In this case, the axis of symmetry passes through nodes, while the conditions of direct or cross-connections are not fulfilled, Fig. 4.4. The nodes on the axis of symmetry are called central nodes.
A symmetry of Form III
A combination of Form II and Form III connections may also exist in a model.
4.6.2 Factorisation of Symmetric Graphs
Once the three types of symmetry are identified, the isomorphic subgraphs S1 and S2 are modified such that the union of eigenvalues of the Laplacian matrices of the two modified subgraphs becomes the same as the eigenvalues of the entire graph S. The process of the modifications applied to the subgraphs is called healing of the subgraphs, and the entire process may be considered as the factorisation of a graph. The subgraphs obtained for a graph S after healings are called the divisor and co-divisor of S. The following operations should be performed for different forms.
Factorisation for Symmetry of Form I: No healing is required, and S1 and S2 are the factors of S.
Factorisation for Symmetry of Form II: For direct connection, link members are removed and S1 resulting in the subgraph C, known as the divisor of S, is obtained. Loops are added to the linked nodes of the subgraph S2 to form the co-divisor D of S.
For cross-connection, after removal of the link members, new members are added between I and J in S1 in order to obtain the divisor C. For S2, k loops are added to each linked node, where k is the number of links connected to that particular linked node. The members between a typical pair of nodes labelled as J + N/2 and I + N/2 are then removed, in order to obtain the co-divisor D.
Factorisation for Symmetry of Form III: The nodes on the axis of symmetry are changed to neutral nodes in S1 to obtain the divisor D. A neutral node is a node which is drawn in the graph; however, it does not take part in the formation of the Laplacian matrix. In order to obtain the co-divisor E, the nodes on the axis of symmetry are added to S2, and each central node is connected to the corresponding linked nodes in S2 by directed members.
The above rules provide simple means for factorising graphs with symmetry. Therefore, simple calculation of eigenvalues of the Laplacian matrices of such graphs becomes feasible.
Example 4.7
Consider the symmetric graph S shown in Fig. 4.5.
A symmetric graph S and its factorisation
The nodes A, B and C in the first subgraph have the corresponding nodes \( \mathrm{{A}}^{\prime} \), \( \mathrm{{B}}^{\prime} \) and \( \mathrm{{C}}^{\prime} \) in the second subgraph. If A, B, C, \( \mathrm{{A}}^{\prime} \), \( \mathrm{{B}}^{\prime} \) and \( \mathrm{{C}}^{\prime} \) are numbered as 1–6, then the Laplacian of S in Fig. 4.5 can be written as follows:
The −1 entries in LI correspond to the link members A\( \mathrm{{A}}^{\prime} \) and C\( \mathrm{{C}}^{\prime} \).
The condensed matrices C and D in this form are obtained as follows:
Matrix C is the same as G with −1 added to its linked nodes A and C, and D is the same as G with −(−1) added to its linked nodes \( \mathrm{{A}}^{\prime} \) and \( \mathrm{{C}}^{\prime} \). Therefore, C and D can be viewed as the Laplacian matrices of two subgraphs C and D as shown in Fig. 4.5, healed with loops being added to D at \( \mathrm{{A}}^{\prime} \) and \( \mathrm{{C}}^{\prime} \). Thus, a factorisation of S is obtained where healings are made to include the effect of link members A\( \mathrm{{A}}^{\prime} \) and C\( \mathrm{{C}}^{\prime} \).
The matrices C and D are calculated as follows:
and
Therefore, in place of finding the eigenvalues of the Laplacian of S, those of C and D can be calculated, and
and
Example 4.8
Consider a graph S with symmetry of Form II and cross-connections, as shown in Fig. 4.6. For this graph the Laplacian matrix is as follows:
A graph S and its factors C and D
In this example, the link members 1–3 and 2–4 have direct connections and 1–4 and 2–3 have cross-connections. Therefore, one loop in node 1 and one in node 2 are produced with respect to direct symmetry, and additional loops are due to the cross symmetry. The deletion of member 1–2 and the addition of an extra member between 3 and 4 are also the healing required because of the cross-connection. The factorisation is shown in Fig. 4.6 and the corresponding C and D matrices are as follows:
Example 4.9
A graph S is considered as shown in Fig. 4.7. The Laplacian of S is a 16 × 16 matrix, which is put in Form II with suitable ordering. The subgraphs corresponding to the condensed submatrices C and D are obtained as shown in Fig. 4.7. Here the members in C with both ends as linked nodes are changed into multiple members, and the linked nodes in D have received the appropriate number of loops. Further decompositions result in the subgraphs illustrated in Fig. 4.7. The eigenvalues are then calculated for the subgraphs as provided in Table 4.1.
A graph S with symmetry and its decomposition
The eigenvalues for the Laplacian L of S are obtained as follows:
Using the symmetry, the Laplacian matrix of S with dimension 16 × 16 having 256 entries is reduced to four matrices of dimension 4 × 4 having counted together 64 entries.
Factorisation for Symmetry of Form IV: Consider the matrix M as given in the example of Sect. 4.4. This matrix can be considered as the Laplacian matrix of the graph G in Fig. 4.8.
A graph and its factors
4.6.3 Form III as an Augmented Form II
Consider the Laplacian for Form II and augment it by a row and a column as follows:
Here, we have no column with equal entries, and the only augmented row is the transpose of the augmented column. Similar to the general case, many augmented rows and columns may be included.
Consider the graph shown in Fig. 4.9:
A graph S
The Laplacian is formed as follows:
where \( \mathbf{G}=[2]\mathrm{and}\mathbf{I}=[-1] \).
The condensed matrices D and E and their eigenvalues are obtained as follows:
and
Hence, \( \left\{ {\uplambda \mathbf{L}\left( \mathrm{S} \right)} \right\}=\left\{ {0,1,4,3} \right\}. \)
In Form III, the matrix L contains a submatrix H corresponding to the symmetric core of the graph. A symmetric core of a graph is a subgraph for which the corresponding Laplacian matrix is of Form II. As an example, for the graph shown in Fig. 4.10, the edge KL is the symmetric core.
A graph with a symmetric core
Node I is linked to nodes K and L in a symmetric manner. K and L are called in-core nodes and I is known as the out-of-core node.
In order to construct Form III, the in-core nodes and the out-of-core nodes should be ordered. In-core nodes are numbered in a suitable manner for Form II, followed by an arbitrary ordering of the out-of-core nodes.
For constructing the graph model of the condensed matrix E, it should be noticed that the addition of the last augmenting row and column results in a nonsymmetric matrix. Therefore, we should define a directed subgraph. In a directed graph, the members are directed, and the degree of a node is the number of arrows leaving that node. A member with two opposing arrows can be treated as a member with no direction.
Example 4.10
Consider the symmetric graph of Fig. 4.11 with an odd number of nodes. This graph has seven nodes and contains a symmetric core of Form II. The additional node A is connected to symmetric nodes 3 and \( {3}^{\prime} \). It can be seen that the symmetry is preserved.
A symmetric graph with seven nodes and its factors D and E
The Laplacian of the graph shown in Fig. 4.11 has Form III. The nodal numbering of the core is the same as for Form II, followed by node A numbered as 7. The corresponding Laplacian has the following pattern:
The corresponding condensed matrices are as follows:
The matrix L without partitioning leads to \( \{\uplambda \mathbf{L}\}=\{\uplambda \mathbf{D}\}\bar{\cup}\{\uplambda \mathbf{E}\}=\left\{ {3,3.7321,3,0.2679,\ 4.4142,1.5858,0} \right\} \). Here, L has 49 entries, while the sum of entries for two condensed matrices D and E is 3 × 3 + 4 × 4 = 25. For cores with higher numbers of nodes, partitioning leads to higher saving in numerical calculations.
In this example, the diagonal entry of D in the third row is 3, while the sum of non-diagonal entries in that row is −2. Here, unlike the condensed matrix of Form II, where the sum of absolute values of non-diagonal entries is bigger than the diagonal entry by an even number, the sum is bigger by an odd number. The reason is that one non-diagonal non-zero entry is in the augmented column which does not take part in the subtraction for calculating D. Therefore, a neutral node is defined as a node which we draw in the graph; however, it does not take part in the formation of the Laplacian matrix.
Example 4.11
For the graph shown in Fig. 4.12, the subgraphs of E and D are illustrated in this figure.
A graph S and its factors D and E
For the subgraph D, the Laplacian and its eigenvalues are as follows:
For the subgraph E, the Laplacian and the corresponding eigenvalues are as follows:
The set of eigenvalues of L is the union of the eigenvalues of E and D.
The main graph has 17 × 17 = 289 entries in L, while the sum of entries of E and D is 9 × 9 + 8 × 8 = 145, which is nearly half of that of L.
4.6.4 Mixed Models
A graph may have different symmetries in the process of sequential decomposition. In the following, examples are considered containing both Form II and Form III symmetries.
Example 4.12
For this example, operations for decomposing and healing are shown in Fig. 4.13, where S is first decomposed to C and D, both being Form III. Then C is decomposed to CD and CE. Similarly, D is decomposed to DD and DE.
A symmetric graphs S and the corresponding decomposition and healing
Example 4.13
For this model, operations for decomposing and healing are shown in Fig. 4.14, where S is first decomposed to C and D having Form II and Form III, respectively. Then C is decomposed to CC and CD, both being Form II. Similarly, D is decomposed to DD and DE, which have Form II and Form III, respectively. CC is decomposed to CCC and CCD, and CD is decomposed to CDC and CDD.
A symmetric graph S, its decomposition and healing
Remark
A graph may contain different symmetries, and an optimal sequence of using these symmetries for decomposition can have a decisive effect on the size and quality of the factors of the graph.
4.7 Graph Representation of Form IV Symmetry
4.7.1 Graph Representation
Matrix [M] can be viewed as the Laplacian matrix of the graph, as shown in Fig. 4.15.
The graph representation of [M] in Eq. 4.35
For [M] in Eq. 4.22, the submatrices \( [{\mathbf{ {e}}_\mathbf{1}}],[{\mathbf{{e}}_\mathbf{2}}] \) and \( [{\mathbf{{e}}_\mathbf{3}}] \) correspond to the subgraphs shown in Fig. 4.16.
A graph and its factors
This graph has two symmetries of Form III, connected to each other by a Form II symmetry. Using the previously developed factorisation method of [1, 2], one obtains the factors as illustrated in Fig. 4.17. The decomposition is performed by a Form II factorisation, followed by a Form III factorisation.
Factorisation of the graph S
A comparison of Figs. 4.16 and 4.17 shows that the factors are quite different. In the latter factorisation, a core is resulted with a matrix having the dimension as \( \frac{\mathrm{N}}{2}\times \frac{\mathrm{N}}{2} \), while the present method results in factors with smaller dimensions.
The graph e3 is a principal factor of S, since its eigenvalues are exactly reflected in those of S, and this is an attractive result for graphs.
Consider six identical subgraphs g, connected by subgraphs c, as shown in Fig. 4.18.
A general sketch of a graph with identical subgraphs
Let \( \left[ {{{\mathbf{L}}_\mathrm{{g}}}} \right] \) be the Laplacian matrix of an internal graph g and [L c] be the Laplacian matrix of the connecting graph c. For a typical internal unit, we have
and for an external unit,
where [\( \mathbf{L}_\mathrm{{c}}^{^{\prime}} \)] is the Laplacian matrix of the external graphs g. The necessary and sufficient condition of the Laplacian of S to have Form IV symmetry is that \( {{\left[ \bf{H} \right]}^\mathrm{{t}}}=[\bf{H}] \). This equality holds when \( \left[ {{{\mathbf{L}}_\mathrm{{c}}}} \right] \) and \( \left[ {\mathbf{L}_\mathrm{{c}}^{^{\prime}}} \right] \) are also symmetric. This form simplifies the eigensolution of grid type of models.
4.7.2 Examples
Example 4.14
Consider the grid G shown in Fig. 4.19.
A simple grid G
The Laplacian matrix L(G) can easily be constructed. For calculating the eigenvalues of L(G), the submatrices [L c] and [H] can be identified as follows:
Now the submatrices of Eq. 4.44 are formed and the corresponding Eigs are calculated:
Eig[M s] is then found as the union of the above eigenvalues. Six factors of the grid are shown in Fig. 4.20a–f. These factors have Form III symmetry and can further be factorised.
The factors of G obtained by operator Eig. (a) \( {{\mathbf{L}}_\mathrm{{c}}} \), (b) \( {{\mathbf{L}}_\mathrm{{c}}}-2\mathbf{H} \), (c) \( {{\mathbf{L}}_\mathrm{{c}}}+\mathbf{H} \), (d) \( {{\mathbf{L}}_\mathrm{{c}}}-\mathbf{H} \), (e) \( {{\mathbf{L}}_\mathrm{{c}}}+\sqrt{3}\mathbf{H} \), (f) \( {{\mathbf{L}}_\mathrm{{c}}}-\sqrt{3}\mathbf{H} \)
Example 4.15
Consider the graph shown in Fig. 4.21. For the numbering provided in this figure, a 48 × 48 Laplacian matrix L(G) can easily be constructed. For calculating the eigenvalues of L(G), the submatrices [L c] and [H] can be expressed as follows:
A graph with circular node and member numbering
The eigenvalues for the factors are obtained as follows:
The eigenvalues of the entire graph is now obtained as the union of the eigenvalues of its factors as Eig[L(G)] =
4.8 Generalised Form III Matrix
Now the question arises whether rows and columns with other properties can be added to the core of a Form II pattern. When the sum of the absolute values for the entries of an augmenting row is the same as that of its column, then D and E can be formed as before. It should be noted that such a restriction is not necessary to be imposed on the last row and column.
Consider the following form:
where P is a real number.
For the ith row,
Example 4.16
Consider a core in Form II:
Add an augmenting row and column to form M with the following properties:
-
1.
Matrix M is symmetric.
-
2.
M has condensed submatrices D and E.
-
3.
Two numerical values are considered for H in M, namely H1 = 4 and H2 = −8.
For H = 4, P is taken arbitrarily as 8, that is,
The condensed submatrices are as follows:
These submatrices will contain the eigen-properties of part of the M.
For H = 8, the numerical value of P is taken as −16, and
The corresponding condensed submatrices are as follows:
As mentioned before, in both M 1 and M 2 matrices some properties of the core are left unaltered. These eigenvalues correspond to those of D. In this example, H = −8, the eigenvalue corresponding to D 1 has this property.
All the properties of Sect. 4.5 are applicable to this special pattern. As an example, the eigenvalues of M 2 are:
It should be mentioned that the above argument is also applicable when k rows and columns are added to the symmetric core of Form II.
4.9 Block Diagonalization of Compound Matrices
In linear algebra it is known that a square matrix can be diagonalised using the normalised eigenvectors, provided all the eigenvectors are orthogonal. It is also proved that if the matrix is Hermitian, then it can be diagonalised and diagonal entries constitute the eigenvalues of this matrix. A matrix is Hermitian if its conjugate is the same as its transpose. Therefore, if a matrix is real, then symmetry is the only requirement for the matrix to be Hermitian. The eigenvalues of Hermitian matrices are real, and the eigenvectors corresponding to any arbitrary pairs of distinct eigenvalues are orthogonal.
If M is a Hermitian matrix, then using U t MU it can be diagonalised. All what is required, is the formation of an orthogonal matrix U. This can in fact be achieved by the singular value decomposition (SVD) approach for symmetric matrices.
Definition
The Kronecker product of two matrices A and B is the matrix we get by replacing the ij, the entry of A by aij B, for all i and j.
As an example,
where entry 1 in the first matrix has been replaced by a complete copy of the second matrix.
Now the main question is how one can block diagonalise a compound matrix. For a matrix M defined as a single Kronecker product, in the form \( \mathbf{M}={{\mathbf{A}}_1}\otimes {{\mathbf{B}}_1} \), it is obvious that if A 1 is Hermitian, then the diagonalisation leads to a block diagonal matrix of the form \( {{\mathbf{D}}_{{{{\mathbf{A}}_1}}}}\otimes {{\mathbf{B}}_1} \).
Now suppose a compound matrix M can be written as the sum of two Kronecker products:
We want to find a matrix P, which diagonalises A 1 and A 2 simultaneously. In such a case, one should show that \( \mathbf{U}=\mathbf{P}\otimes \mathbf{I} \) block diagonalises M, that is, we have to show that U t MU is a block diagonal matrix.
From algebra we have \( {{\left( {\mathbf{A}\otimes \mathbf{B}} \right)}^\mathrm{{t}}}={{\mathbf{A}}^\mathrm{{t}}}\otimes {{\mathbf{B}}^\mathrm{{t}}} \) and \( (\mathbf{A}\otimes \mathbf{B})(\mathbf{C}\otimes \mathbf{D})=\mathbf{AC}\otimes \mathbf{B}\mathbf{D} \). Then
Since it is assumed that P diagonalises A 1 and A 2, thus
and therefore,
In this way, U becomes block diagonalised and in order to calculate the eigenvalues of M, one can evaluate the eigenvalues of the blocks on the diagonal. The matrices M and U t MU are similar matrices, since P is orthogonal, thus U is also orthogonal and its inverse is equal to its transpose.
Now an important question is whether the assumptions made at the beginning of this section are feasible; that is, can one always find a matrix P, which diagonalises A 1 and A 2 simultaneously?
For a matrix to be diagonalisable, it is necessary to be Hermitian. However, for two matrices to be diagonalisable, not only these two matrices should be Hermitian, but these matrices should also commute [10]; that is,
Therefore, if A 1 and A 2 commute with respect to multiplication, then
The \( {\uplambda_\mathrm{{i}}}\left( {{{\mathbf{A}}_\mathrm{{j}}}} \right) \) for j = 1,2 is a diagonal matrix containing all the eigenvalues of A j, and n is the dimension of the matrix A i. It should be noticed that the order of the eigenvalues in A 1 and A 2 is important. The order is the same as obtained after simultaneous diagonalisation of the two matrices, which appear on the diagonal of the matrices.
As an example, for the special case with A 1 = I, it is obvious that IA 2 = A 2 I, and we have
These special cases are already shown in early sections of this chapter.
One can use another A 1 matrix except I, provided it commutes with respect to A 2. The Hermitian property is obvious, due to the symmetry, and it is real; though for complex matrices this property still holds. For the formation of P, it is sufficient to use SVD decomposition for a linear combination of A 1 and A 2, that is, if we use the SVD decomposition on \( \mathbf{N}={\mathrm{{a}}_1}{{\mathbf{A}}_1}+{\mathrm{{a}}_2}{{\mathbf{A}}_2} \), then P can be obtained; here, a1 and a2 are two arbitrary nonequal numbers.
As an example, consider the following matrix which has the Form II form:
Since I and T commute, one can, for example, decompose \( \mathbf{N}=2\mathbf{I}+\mathbf{T} \). Here, I and T have much smaller dimensions compared to that of M, and in this particular case, these are 2 × 2 matrices. Decomposition of N leads to
Therefore, it is only necessary to calculate the eigenvalues of A + B and A − B, and if the diagonal entries are not needed, then using Eq. 4.63
As another example, consider a matrix M in the following form:
As before, P can be obtained from a linear combination of I and T as follows:
Using Eq. 4.66 leads to
The interesting point about the matrices of the above form is that the determinant of the matrix is calculated after they are put in block forms, decomposition is performed, and the components are then obtained. As the first example, consider
and as the second example consider
It should be noted that here blocks are treated as numbers, that is, these have the commuting property. In general, one can show that
Comparing with Eq. 4.63, we have \( {\upalpha_\mathrm{{i}}}={\uplambda_\mathrm{{T}}}. \) Since \( \mathbf{T}=\mathbf{F}(0,1,0) \), therefore as mentioned before, we have \( {\upalpha_\mathrm{{i}}}={\uplambda_{\mathbf{T}}}=2\cos \frac{\mathrm{{k}\uppi}}{\mathrm{{n}+1}} \), where k = 1:n.
Applications of these relationships will be demonstrated in Examples 7.20 and 7.21 of Chap. 7. As it will be shown, one may need to multiply rows or columns with certain numbers to transform the matrix into the above form.
The present approach is always applicable. As an example, consider the following matrix:
which is a block penta-diagonal matrix and can be presented more simply by F matrices as
Here M shown by an F matrix in a similar manner to that of Eq. 4.72, The only difference is that in this case an additional argument is introduced, which is the magnitude of the entries in the additional diagonals introduced compared to a tri-diagonal matrix.
It can be shown that S and T are not unit matrices, and therefore, Eq. 4.63 is not applicable. However, since TS = ST, thus Eq. 4.62 should be employed.
As an example, for m = 8 and n = 5, instead of calculating the eigenvalues of a 40 × 40 matrix, the eigenvalues of five 8 × 8 matrices will be needed, since T and S commute and M is block diagonalisable.
4.10 Matrices as the Sum of Three Kronecker Products
Now we assume M to be the sum of three Kronecker products as
If the block diagonalisation of M is required, as for the case with two terms, A i (i = 1:3) should commute for any two matrices A i, that is,
With these conditions holding, the matrix M can be transformed into tri-diagonal matrix and then to a diagonal matrix.
Consider a penta-diagonal matrix as
where
Here, \( {{\mathbf{A}}_\mathrm{{i}}}{{\mathbf{A}}_\mathrm{{j}}}={{\mathbf{A}}_\mathrm{{j}}}{{\mathbf{A}}_\mathrm{{i}}}\kern1em \mathrm{i},\mathrm{j}=1:3,\kern0.5em \mathrm{i}\ne \mathrm{j} \) holds and M can be diagonalised. A matrix with numerical entries can be decomposed by SVD to obtain P. Then \( \mathbf{U}=\mathbf{P}\otimes \mathbf{I} \) is selected (e.g. N = A 1 + 2A 2 + 3A 3) as
resulting in a block matrix U t MU. Therefore, instead of calculating U, we calculate the block matrices by
In order to demonstrate the applications, in Examples 7.22 and 7.23 of Chap. 7, a plate will be studied under uniaxial forces, and their buckling loads will be calculated. Example 7.24 will study the natural frequency of a system with continuous distributed mass.
4.11 The Commutating Condition
In this section, the condition for two matrices of the form F to commute is investigated.
Theorem 1
For two penta-diagonal (tri-diagonal as a special case) matrices of the form \( {{\mathbf{A}}_\mathrm{{i}}}=\mathbf{F}({\mathrm{{a}}_\mathrm{{i}}},{\mathrm{{b}}_\mathrm{{i}}},{\mathrm{{c}}_\mathrm{{i}}},{\mathrm{{d}}_\mathrm{{i}}}),{{\mathbf{A}}_\mathrm{{i}}}{{\mathbf{A}}_\mathrm{{j}}}={{\mathbf{A}}_\mathrm{{j}}}{{\mathbf{A}}_\mathrm{{i}}}\mathrm{if}\ {\mathrm{{t}}_1}=\frac{{{\mathrm{{a}}_\mathrm{{i}}}-{\mathrm{{c}}_\mathrm{{i}}}}}{{{\mathrm{{d}}_\mathrm{{i}}}}}\kern0.5em \mathrm{and}\ {\mathrm{{t}}_2}=\frac{{{\mathrm{{a}}_\mathrm{{i}}}-{\mathrm{{c}}_\mathrm{{i}}}+{\mathrm{{d}}_\mathrm{{i}}}}}{{{\mathrm{{b}}_\mathrm{{i}}}}} \) for both matrices A i and A j are identical.
Proof
Consider
ai to di are all numbers. From definition of t1 and t2, we have
Substituting A i we obtain
In the last three terms, di is factorised and R is obtained. If t1 and t2 are the same for both matrices, then they have identical R, and it is only necessary to show that
This is obvious since I and R commute and R 2 can be cancelled from two sides. The proof is then complete.
It should be noted that if one of the above expressions for t1 and t2 becomes \( \frac{0}{0} \), then the condition for commuting will hold and no control is required. We also consider the result of dividing two nonequal numbers as non-zero. Therefore, for two tri-diagonal matrices, the above condition holds for t1’s (since the divisor is always zero and the magnitude of dividend is not important), and t2’s should be equal. As an example, in Example 7.22 we will have
Since t1 of the matrix T is equal to \( \frac{0}{0} \), thus there is no need to calculate t1 of S, and also \( {\mathrm{{t}}_2}=\frac{0}{0} \) for S. Therefore, these two matrices (S and T) commute. One can also control T, I, S, I for commuting. However, in Example 7.23, it will be seen that after block diagonalisation, M is transformed into N, and N does not satisfy the above condition, since
t1 requires no control; however, t2 for S and T are not identical. Therefore, no further simplification can be made for N. While in Example 7.22, N had S and T similar to M, and we can reduce it into simple non-matrix equation.
4.12 A Block Tri-diagonal Matrix with Corner Blocks and Its Block Diagonalisation
In this section, a canonical form is introduced and an efficient method is developed for its block diagonalisation.
Consider a matrix M as
This matrix is a block symmetric matrix which has \( n\times n \) blocks. The blocks of this matrix are \( {{\mathbf{A}}_{{m\times m}}},{{\mathbf{B}}_{{m\times m}}} \) and \( \mathrm\mathbf{B}_{{m\times m}}^{\mathrm{ t}} \); thus, this matrix generally has \( nm\times nm \) entries. Block \( \mathbf{A} \) is located on the main diagonal and blocks \( \mathbf{B} \) and \( {{\mathbf{B}}^\mathrm{ t}} \) are situated on the upper and lower adjacent diagonals and also in the lower-left corner and the upper-right corner, respectively.
The problem is to find the eigenvalues and eigenvectors of \( \mathbf{M} \). This matrix is symmetric and a set of \( \mathrm{nm} \) real eigenvalues \( {\mu_\mathrm{{i}}} \) and real eigenvectors \( {\mathbf{\upvarphi}_\mathrm{{i}}} \) can be calculated in such a manner that \( \mathbf{M}{\mathbf{\upvarphi}_\mathrm{{i}}}={\upmu_\mathrm{{i}}}{\mathbf{\upvarphi}_\mathrm{{i}}} \) (\( \mathrm{i}=1,\ldots,nm \)). Now, using the decomposed form of \( \mathbf{M} \), an efficient method is presented for its eigensolution.
Matrix \( \mathbf{M} \) can be decomposed as the sum of three Kronecker products:
where, \( \mathbf{I} \) is an \( \mathrm{n}\times \mathrm{n} \) identity matrix and \( \mathbf{H} \) is an \( \mathrm{n}\times \mathrm{n} \) unsymmetric matrix as
Since \( \mathbf{H} \) is unsymmetric, the block diagonalisation of \( \mathbf{M} \) needs additional considerations. Firstly, \( \mathbf{H} \) is a permutation matrix and thus it is orthogonal. Therefore,
Secondly, \( \mathbf{H} \) and \( {{\mathbf{H}}^{\mathbf{t}}} \) have commutative property. On the other hand
This means that these two matrices can simultaneously be diagonalised. Now, using a matrix such as \( \mathbf{U}=\mathbf{X}\otimes \mathbf{I} \), \( \mathbf{M} \) is diagonalised.
Since a similarity transformation is used, thus the eigenvalues do not change. In Eq. 4.94, \( \mathbf{I} \) is a diagonal matrix and it is sufficient to show that \( \mathbf{X} \) diagonalises H and \( {{\mathbf{H}}^{\mathbf{t}}} \). On the other hand, it is assumed that
in which \( {{\mathbf{D}}_1} \) and \( {{\mathbf{D}}_2} \) are diagonal matrices. Thus, the block diagonal form of \( \mathbf{M} \) can be written as
Generally, Eqs. 4.95 and 4.96 are eigenvalue decomposition of matrices \( \mathbf{H} \) and \( {{\mathbf{H}}^{\mathbf{t}}} \) in which \( \mathbf{X} \) and \( \mathbf{D} \) are eigenvector and eigenvalue matrices, respectively. Since \( \mathbf{H} \) is orthogonal, a relationship between \( {{\mathbf{D}}_1} \) and \( {{\mathbf{D}}_2} \) can be established. If we find the inverse of Eq. 4.95, then with respect to the orthogonal property of \( \mathbf{H} \), we will have
Thus,
Now the eigenvalues and eigenvectors of matrix \( \mathbf{H} \) (entries of \( \mathbf{D} \) and \( \mathbf{X} \)) are analytically calculated. As previously mentioned, \( \mathbf{H} \) is an \( n\times n \) permutation matrix and its characteristic polynomial (using variable \( \uplambda \)) can be written as
In general, Eq. 4.101 has \( \mathrm{n} \) real and complex roots. It is clear that if \( \mathrm{n} \) is even or odd, then (−1, 1) and (1) are only real roots of Eq. 4.101, respectively. Other complex roots of this equation can easily be calculated. Since the absolute value of each root is unit, therefore the roots of Eq. 4.101 are identical to those of Eq. 4.102.
These complex and real roots are presented in Table 4.2.
According to Table 4.2, depending on \( \mathrm{n} \) being even or odd, two real and \( \mathrm{ n}-2 \) complex roots or a real and \( \mathrm n-1 \) complex roots should be calculated, respectively. In addition, the normalised eigenvectors \( {{\mathbf{x}}^i} \) associated with the eigenvalues \( {\uplambda_\mathrm{{i}}}\left( \mathrm{{i}=1,\ldots,n} \right) \) can analytically be evaluated by solving the following equation:
This is a linear equation and by selecting \( {{\mathbf{x}}_1} \), all other entries of \( {{\mathbf{x}}^i} \) (unknown eigenvector) are found as follows:
It is important to note that if \( {{\mathbf{x}}_1}=\frac{1}{{\sqrt\mathrm{{n}}}} \) is assumed, each eigenvector will be calculated in a normalised form with no additional effort. Also the matrix \( \mathbf{X} \) with its columns being the eigenvectors of \( \mathbf{H} \), can easily be generated as
Now, Eq. 4.97 can be expressed in a much simpler form. Since \( {\uplambda_\mathrm{{i}}} \)s are located on the diagonal entries of \( \mathbf{D}\left( {{\mathrm{{d}}_\mathrm{{i}\mathrm{i}}}={\uplambda_\mathrm{{i}}}} \right) \), and the absolute value of each \( {\uplambda_\mathrm{{i}}} \) is unit, thus, the inverse of the complex diagonal matrix equals to its conjugate, and Eq. 4.100 can simply be written as
Finally, according to Eq. 4.108, the eigenvalues of matrix \( \mathbf{M} \) can be found using the union of the eigenvalues of \( \mathrm{n} \) blocks as
where \( \left( {\mathbf{B}{{\mathbf{L}}_j}} \right) \) is the jth diagonal block of \( {{\mathbf{U}}^{-1 }}\mathbf{MU} \) associated with \( {\uplambda_\mathrm{ j}} \), that is, the calculation of the eigenvalues of an \( nm\times nm \) matrix is transformed into those of \( \mathrm n \) times \( m\times m \) matrices. Clearly, this process leads to a significant decrease in computational time and memory.
Also, for each eigenvalue \( {\upmu_\mathrm{ i}} \) which is obtained from Eq. 4.108 (for the jth block), an eigenvector \( {\mathrm{{y}}_\mathrm{ i}} \) is calculated as
This eigenvector can easily be transformed into an eigenvector of \( \mathbf{M} \) using the following relationships:
Therefore, if \( {\upmu_\mathrm{ i}} \) is a simple root of characteristic polynomial corresponding to \( \mathbf{M} \), Eq. 4.111 leads to an eigenvector with real entries. However, if \( {\upmu_\mathrm{ i}} \) is a multiple root of characteristic polynomial, Eq. 4.111 leads to eigenvectors with complex entries. As we know, \( {\uplambda_\mathrm{ j}}\ \mathrm{and}\ {{\overline{\uplambda}}_j} \) are the roots of Eq. 4.101, leading to two conjugate blocks \( \left( {\mathbf{B}{{\mathbf{L}}_\mathrm{ j}}} \right) \) which have identical eigenvalues, and their conjugate eigenvectors are found by Eq. 4.111. For such eigenvalues, the eigenvectors with real entries can be generated. This is done by simply adding two complex conjugate eigenvectors. Obviously, the imaginary parts of these two vectors will be eliminated. The remaining vector is also orthogonal to other eigenvectors and should be normalised. However, other orthogonal real eigenvectors for multiple eigenvalues should be calculated by an orthogonalisation algorithm, such as Gram–Schmidt method [11], if needed.
References
Kaveh A, Sayarinejad MA (2003) Eigensolutions for matrices of special structures. Commun Numer Methods Eng 19:125–136
Kaveh A, Sayarinejad MA (2004) Eigensolutions for factorable matrices of special patterns. Commun Numer Methods Eng 20(2):133–146
Kaveh A, Sayarinejad MA (2005) Eigenvalues of factorable matrices with Form IV symmetry. Commun Numer Methods Eng 21(6):269–278
Kaveh A, Sayarinejad MA (2006) Augmented canonical forms and factorization of graphs. Int J Numer Methods Eng 65(10):1545–1560
Kaveh A, Sayarinejad MA (2006) Eigensolution of specially structured matrices with hyper-symmetry. Int J Numer Methods Eng 67(7):1012–1043
Rempel J, Schwolow KH (1977) Ein Verfahren zur Faktorisierung des charakteristiscen Polynoms eines Graphen. Wissenschaftliche Zeitschrift der TH Ilmenau 23:25–39
Cvetkovié DM, Doob M, Sachs H (1980) Spectra of graphs. Academic, New York
Kaveh A, Rahami H (2007) Compound matrix block diagonalization for efficient solution of eigenproblems in structural matrices. Acta Mech 188(3–4):155–166
Kaveh A, Rahami H (2006) Unification of three canonical forms with application to stability analysis. Asian J Civil Eng 7(2):125–138
Kaveh A, Rahami H (2006) Block digonalization of adjacency and Laplacian matrices for graph products; applications in structural mechanics. Int J Numer Methods Eng 68:33–63
Jacques I, Judd C (1987) Numerical analysis. Chapman and Hall, London
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Wien
About this chapter
Cite this chapter
Kaveh, A. (2013). Canonical Forms, Basic Definitions and Properties. In: Optimal Analysis of Structures by Concepts of Symmetry and Regularity. Springer, Vienna. https://doi.org/10.1007/978-3-7091-1565-7_4
Download citation
DOI: https://doi.org/10.1007/978-3-7091-1565-7_4
Published:
Publisher Name: Springer, Vienna
Print ISBN: 978-3-7091-1564-0
Online ISBN: 978-3-7091-1565-7
eBook Packages: EngineeringEngineering (R0)