Classes of Digraph Structures Corresponding to Characteristic Polynomials

Abstract

This paper introduces the first classification of digraph structures corresponding to characteristic polynomials. It was found that digraph structures created can be divided into three classes with different feasibility for different polynomials—only structures of one class are found to be independent from wages of polynomial’s terms. In this paper classification of structures is described, along with method how to divide them and illustrated with examples.

Research has been financed with the funds of the Statutory Research of 2016.

1 Introduction

In last 2 years there was presented parallel algorithm for finding the determination of characteristic polynomial realisations of dynamic systems based on multi-dimensional digraphs theory [5]. It is an alternative to canonical forms of the system [8], i.e. constant matrix forms, which satisfy the system described by the transfer function. With the use of those forms, we are able to write only one realisation of the system, while algorithm presented in [5] allows for finding all possible sets of matrices which fit into the system transfer function [6, 7]. The digraph theory was applied to the analysis of dynamical systems. The use of multi-dimensional digraph theory was proposed for the first time in the paper [4] to the analysis of positive two-dimensional systems.

Still, multi-dimensional digraphs used for characteristic polynomial realisations are not fully defined and determined—and there is space for further research about properties of possible solutions obtained. It is known that some structures obtained won’t satisfy the polynomial or there will be need for solving a system of polynomial equations to determine the coefficients of state matrices from them. The scope of this article is to examine structures that do not generate the solution instantly (i.e. just by examination of the digraph) to find all possible proper digraph structures for the characteristic polynomial.

Notion. In this paper the following notion will be used. The set $n\times m$ real matrices will be denoted by $\mathbb {R}^{n \times m}$ and $\mathbb {R}^{n}=\mathbb {R}^{n \times 1}$. If $\mathbf {G}=[g_{ij}]$ is a matrix, we write $\mathbf {G}\geqslant 0$ (matrix $\mathbf {G}$ is called non-negative), if $g_{ij}\geqslant 0$ for all i, j; $\mathbf {G}>0$ (matrix $\mathbf {G}$ is called positive), if $\mathbf {G}\geqslant 0$ and any $g_{ij}> 0$; $\mathbf {G}\gg 0$ (matrix $\mathbf {G}$ is called strictly positive), if $g_{ij}>0$ for all i, j. The set of $n \times m$ real matrices with non-negative entries will be denoted by $\mathbb {R}_{+}^{n \times m}$ and $\mathbb {R}_{+}^{n}=\mathbb {R}_{+}^{n \times 1}$. The $n \times n$ identity matrix will be denoted by $\mathbf {I}_{n}$.

1.1 Characteristic Polynomial

Let $\mathbb {F}$ be a field e.g., of the real number $\mathbb {R}$. The function $P(w_{1},w_{2},\ldots ,w_{j})$ of the variable $w_{1}, w_{2}, \ldots , w_{j}$, where $j=1,2,\ldots ,\infty$

$$\begin{aligned} p(w_{1},w_{2},\ldots , w_{j})=w_{1}^{n_{1}}w_{2}^{n_{2}}\ldots w_{j}^{n_{j}}-\sum _{i_{1}=0}^{n_{1}}\sum _{i_{2}=0}^{n_{2}}\ldots \sum _{i_{j}=0}^{n_{j}}a_{i_{1},i_{2},\ldots i_{j}}w_{1}^{i_{1}}w_{2}^{i_{2}}\ldots w_{j}^{i_{j}} \end{aligned}$$

(1)

is called polynomial $p(w_{1},w_{2},\ldots , w_{j})$ in the variable $w_{1}, w_{2}, \ldots , w_{j}$, over the field $\mathbb {F}$, where $a_{i_{1},i_{2},\ldots ,i_{j}}\in \mathbb {F}$ for $i=0,1,2,\ldots , n$ and for $j=1,2,\ldots ,\infty$ are called the coefficients of the polynomial.

The set of polynomial (1) over the field $\mathbb {F}$ will be denoted by $\mathbb {F}[w_{1},w_{2},\ldots ,w_{j}]$ where $j=1,2,\ldots ,\infty$.

If $a_{n_{1},n_{2},\ldots ,n_{j}} \ne 0$, then the non-negative integral $n=n_{1}+n_{2}+\cdots +n_{j}$ is called the degree of a polynomial and is denoted $deg\,p(w_{1},w_{2},\ldots ,w_{j})$, i.e., $n=deg\,p(w_{1},w_{2},\ldots ,w_{j})$. The polynomial is called monic, if $a_{n_{1},n_{2},\ldots ,n_{j}}=1$ and zero polynomial, if $a_{i_{1},i_{2},\ldots ,i_{j}}=0$ for $i=0,1,\ldots ,n$ and for $j=1,2,\ldots ,\infty$.

Interested reader may find definition and properties of the characteristic polynomial in books on linear algebra, for example in [2, Chap. 9].

Remark 1

If we consider one-dimensional discrete-time system described by the equations: $x_{i+1}=\mathbf {A}x_{i}+\mathbf {B}u_{i}$; $y_{i}=\mathbf {C}x_{i}+\mathbf {D}u_{i}$ for $i\in \mathbb {Z}_{+}$ then, characteristic polynomial (1) consist from one variable z and have the form: $d(z)=z^{n}-\sum _{i=0}^{n}d_{i}z^{i}=z^{n}-d_{n-1}z^{n-1}-\cdots -d_{1}z-d_{0}$. Similarly, characteristic polynomial consist from variable s, if we consider one-dimensional continuous-time system.

Remark 2

If we consider two-dimensional discrete-time system described by the equations: $x_{i+1,j+1}=\mathbf {A}_{1}x_{i+1,j}+\mathbf {A}_{2}x_{i,j+1}+\mathbf {B}_{1}u_{i+1,j}+\mathbf {B}_{2}u_{i,j+1}$; $y_{ij}=\mathbf {C}x_{ij}+\mathbf {D}u_{ij}$ for $i\in \mathbb {Z}_{+}$ and $j\in \mathbb {Z}_{+}$ then, characteristic polynomial (1) consist from two variables $z_{1}$ and $z_{2}$ and have the form: $d(z_{1},z_{2})=z_{1}^{n}z_{2}^{n}-\sum _{i=0}^{n}\sum _{j=0}^{n}d_{ij}z_{1}^{i}z_{2}^{j}=z_{1}^{n}z_{2}^{n}-d_{n-1,n}z_{1}^{n-1}z_{2}^{n}-d_{n,n-1}z_{1}^{n}z_{2}^{n-1}-\cdots -d_{10}z_{1}-d_{01}z_{2}-d_{00}$. Similarly, characteristic polynomial consist from variables: $s_{1}$ and $s_{2}$ if we consider two-dimensional continuous-time system; s and z if we consider hybrid system. In an analogous way we proceed with higher dimensions systems.

1.2 Digraphs

A directed graph (called also digraph) $\mathfrak {D}$ consists of a non-empty finite set $\mathbb {V}(\mathfrak {D})$ of elements called vertices and a finite set $\mathbb {A}(\mathfrak {D})$ of ordered pairs of distinct vertices called arcs. We call $\mathbb {V}(\mathfrak {D})$ the vertex set and $\mathbb {A}(\mathfrak {D})$ the arc set of $\mathfrak {D}$. We will often write $\mathfrak {D} = (\mathbb {V},\mathbb {A})$ which means that $\mathbb {V}$ and $\mathbb {A}$ are the vertex set and arc set of $\mathfrak {D}$, respectively. The order of $\mathfrak {D}$ is the number of vertices in $\mathfrak {D}$. The size of $\mathfrak {D}$ is the number of arc in $\mathfrak {D}$. For an arc $(v_{1},v_{2})$, the first vertex $v_{1}$ is its tail and the second vertex $v_{2}$ is its head. More information about digraph theory is given in [1, 9]. A two-dimensional digraphs $\mathfrak {D}^{(2)}$ is a directed graph with two types of arcs and input flows. For the first time, this type of digraph was presented in [3, 4]. When we generalise this approach, we can define n-dimensional digraphs $\mathfrak {D}^{n}$ in the following form.

Definition 1

An n-dimensional digraphs $\mathfrak {D}^{(n)}$ is a directed graph with q types of arcs and input flows. In detail, it is $(\mathbb {S}, \mathbb {V}, \mathfrak {A}_{1}, \mathfrak {A}_{2},\ldots , \mathfrak {A}_{q}, \mathfrak {B}_{1}, \mathfrak {B}_{2}, \ldots , \mathfrak {B}_{q} )$, where $\mathbb {S}=\{s_{1},s_{2},\ldots , s_{m}\}$ is the set of sources, $\mathbb {V}=\{v_{1}, v_{2}, \ldots ,v_{n}\}$ is the set of vertices, $\mathfrak {A}_{1}$, $\mathfrak {A}_{2}$, $\ldots$, $\mathfrak {A}_{q}$ are the subsets of $\mathbb {V} \times \mathbb {V}$ which elements are called $\mathfrak {A}_{1}$-arcs, $\mathfrak {A}_{2}$-arcs, $\ldots$, $\mathfrak {A}_{q}$-arcs respectively, $\mathfrak {B}_{1}$, $\mathfrak {B}_{2}$, $\ldots$, $\mathfrak {B}_{q}$ are the subsets of $\mathbb {S}\times \mathbb {V}$ which elements are called $\mathfrak {B}_{1}$-arcs, $\mathfrak {B}_{2}$-arcs, $\ldots$, $\mathfrak {B}_{q}$-arcs respectively.

There exists $\mathfrak {A}_{1}$-arc ($\mathfrak {A}_{2}$-arc, $\ldots$, $\mathfrak {A}_{q}$-arc) from vertex $v_{j}$ to vertex $v_{i}$ if and only if the (i, j)-th entry of the matrix $\mathbf {A}_{1}$ ($\mathbf {A}_{2}$, $\ldots$, $\mathbf {A}_{q}$) is non-zero. There exists $\mathfrak {B}_{1}$-arc ($\mathfrak {B}_{2}$-arc, $\ldots$, $\mathfrak {B}_{q}$-arc) from source $s_{l}$ to vertex $v_{j}$ if and only if the l-th entry of the matrix $\mathbf {B}_{1}$ ($\mathbf {B}_{2}$, $\ldots$, $\mathbf {B}_{q}$) is non-zero.

Remark 3

$\mathfrak {A}_{q}$-arcs and $\mathfrak {B}_{q}$-arcs, are drawn by the other colour or line style.

Example 1

For the system described by the matrices

(2)

we can draw digraphs $\mathfrak {D}^{(3)}$ consisting from vertices $v_{1}, v_{2}, v_{3}$ and source $s_{1}$. Digraph corresponding to system (2) is presented on Fig. 1.

 

Fig. 1

Three-dimensional digraphs $\mathfrak {D}^{(3)}$ corresponding to matrices (2)

1.3 Digraph Creation

The digraph creation algorithm introduced in [5] starts with creating digraphs for all monomials in the characteristic polynomial, then joins them by the use of disjoint union to create all possible variants of digraphs representing the polynomial realisation. When multiplying the characteristic polynomial (1) by $w_{1}^{-n_{1}}w_{2}^{-n_{2}}\ldots w_{j}^{-n_{j}}$ for $j=1,2,\ldots \infty$, we obtain

$$\begin{aligned} p\left( w_{1},w_{2},\ldots ,w_{j}\right) =1-\sum _{i_{1}=0}^{n_{1}}\sum _{i_{2}=1}^{n_{2}}\ldots \sum _{i_{j}=0}^{n_{j}}a_{i_{1}i_{2}\ldots i_{j}}w_{1}^{i_{1}-n_{1}}w_{2}^{i_{2}-n_{2}}\ldots w_{j}^{i_{j}-n_{j}} \end{aligned}$$

(3)

The method finds state matrices $\mathbf {A}_{k}$, $k=1,2,\ldots ,\infty$ using decomposing characteristic polynomial (3). In the first step, we decompose polynomial (3) into a set of simple monomials $M_1$, ..., $M_j$. The factor of 1 is a special case, as it is used in the topology to represent digraph vertices, so polynomial (3) can be represented as

$$\begin{aligned} p\left( w_{1},w_{2},\ldots ,w_{j}\right) =1 - M_1 - \cdots - M_j. \end{aligned}$$

(4)

For each of monomials $M_1$, ..., $M_j$ we create digraph representation that consists of n vertices and one n-arc cycle, where n is a sum of powers of all variables of the monomial. Each monomial digraph in fact represents a simple polynomial digraph $1-M_i$, $i=1,\ldots ,j$. After creation of all digraph representations of monomials in the polynomial, we can determine all possible characteristic polynomial realisations using all combinations of the digraph monomial representations. Finally, we combine received digraphs into one digraph which is corresponding to the characteristic polynomial (3) by disjoint union of monomial digraphs.

Example 2

Lets take polynomial $p_1(z_1, z_2) = 1-z_{1}^{-2}z_2^{-1}-z_{1}^{-1}z_2^{-1}$. To create digraph representation for it we need first to create digraph representation for two monomials. Representation for the first monomial is presented on Fig. 2a and for the second on Fig. 2b. For simple polynomial $p_2(z_1, z_2) = 1-z_{1}^{-2}z_2^{-1}$ digraph representation would be the same as for monomial (and presented on Fig. 2a). To achieve digraph representation for our polynomial $p_1$ we need to add digraph representations of monomials by means of disjoint union (without creation of multiarcs of the same colour). On Fig. 2c presented is one of possible digraph representations for polynomial $p_1$. Another, presented on Fig. 2d, can be obtained by adding second monomial to vertices 2 and 3 instead of vertices 1 and 2. As can be seen those aren’t all the possible representations of polynomial $p_1$.

Fig. 2

a Digraph $\mathfrak {D}^{(2)}_{1}$ corresponding to polynomial $1-z_{1}^{-2}z_2^{-1}$; b Digraph $\mathfrak {D}^{(2)}_{2}$ corresponding to polynomial $1-z_{1}^{-1}z_2^{-1}$; Sample polynomial digraph: corresponding to union of digraphs c $\mathfrak {D}_{3}^{(2)}=\mathfrak {D}^{(2)}_{1} + \mathfrak {D}^{(2)}_{2}$; d $\mathfrak {D}_{4}^{(2)}= \mathfrak {D}^{(2)}_{1} + \mathfrak {D}^{(2)}_{2}$

2 Problem Formulation

The algorithm presented in [5, 7] is based on the multi-dimensional digraph theory to allow the creation of a complete set of solutions of characteristic polynomial realisations—this is what differs the method from other state-of-the-art solutions like canonical forms, as they are capable of finding only a few of existing realisations. As algorithm is able to find all the possible structures there is the need of checking the validity of them, as not all digraph structures created from monomial sub-graphs, according to the principles presented in Sect. 1.3, are a valid digraph representation of the characteristic polynomial. From some of them it is impossible to obtain state matrices that will satisfy the polynomial, while others generate solutions for which it is needed to get the coefficients of state matrices by solving a system of polynomial equations that in some cases can be under-determined. Those structures were in previous articles marked as invalid for reasons of different method of solving, slowing down the algorithm or removing the advantage of checking the matrix structure directly from digraph, but need to be examined in more detail to find all possible proper digraph structures for the characteristic polynomial and that is the scope of this article.

3 Classes of Digraph Structures

Extensive study and experimentation shoved that obtained digraph structures can be grouped into three classes. Some structures are valid for all possible coefficients of characteristic polynomial (given in symbolic form) and have minimal number of arcs needed. Those structures were examined in detail in [7] and here are denoted as class $\mathcal {K}_1$. Some structures give proper solution for given coefficients of characteristic polynomial—their structure can contain some additional arcs and there is need to solve a set of linear equations to get wages of digraph arcs. Those are denoted as class $\mathcal {K}_3$. And there are structures that cannot guarantee proper solution for given characteristic polynomial (or in some specific cases we are unable to determine if the solution is possible) that are denoted as class $\mathcal {K}_2$. Figure 3 illustrates how we determine to which class given digraph structure belongs. Conditions $S_1$, $S_2$ and $S_3$ presented on the Fig. 3 are stated below.

Fig. 3

Classes structure

Condition $S_1$: There exist positive state matrices of the discrete time linear system corresponding to the characteristic polynomial (3) if for digraph $\mathfrak {D}^{(n)}$ = $\mathfrak {D}^{(n)}_1 + \mathfrak {D}^{(n)}_2 + \cdots + \mathfrak {D}^{(n)}_M$ all of the following conditions are met:

• ($S_{1a}$): $\mathbb {V}_1 \cap \mathbb {V}_2 \cap \cdots \cap \mathbb {V}_M \ne \{\emptyset \}$,

• ($S_{1b}$): the number of cycles in digraph $\mathfrak {D}^{(n)}$ equals M;

where M is a number of monomials in characteristic polynomial and $\mathbb {V}_k$ is a set of vertices of digraph $\mathfrak {D}^{(n)}_k$ of k-th monomial.

Condition $S_2$: Every digraph structure belongs to class $\mathcal {K}_2$ and cannot satisfy the given characteristic polynomial (3) if there exists a single cycle that is representing any of terms that is not existing in that polynomial (i.e. has its $a_{i_n}$ wage equal to zero).

Condition $S_3$: If for every term not existing in characteristic polynomial (3) (i.e. with $a_{i_n}$ wage equal to zero) there exist none or at least two cycles corresponding to that term and the resultant system of equations is not under-determined (i.e. the number of unknowns does not outnumber the number of equations) we can determine the wages for all arcs that satisfy given characteristic polynomial and digraph structure belongs to class $\mathcal {K}_3$.

Class $\mathcal {K}_{1}$: Digraph structures belonging to class $\mathcal {K}_1$ satisfy all characteristic polynomials of given type (with the same number and power of terms) for any $a_{i_1, i_2,\ldots , i_j} != 0$ wages. Those are digraph structures that are the most thoroughly examined in previous papers and that can be computed quickly using digraph-based GPGPU (General-Purpose Computation on Graphics Processing Units) methods as there is no need of solving a system of polynomial equations.

Class $\mathcal {K}_{2}$: Digraph structures belonging to class $\mathcal {K}_2$ cannot satisfy the given characteristic polynomial (or we are unable to determine the solution due to problem with solving a system of under-determined equations) and are considered invalid for given characteristic polynomial. It is worth noting that in case of fulfilling $S_2$ condition such structures will be improper solutions for all characteristic polynomials with the same terms, no matter the $a_{i_1, i_2,\ldots , i_j} != 0$ wages and in case of not fulfilling $S_3$ condition such structures are only improper for given wages of characteristic polynomial and possibly can be made proper with change of wages of characteristic polynomial’s terms.

Class $\mathcal {K}_{3}$: Digraph structures belonging to class $\mathcal {K}_3$ satisfy given characteristic polynomial with specific $a_{i_1, i_2,\ldots , i_j}$ wages, but unlike class $\mathcal {K}_1$ structures cannot be computed directly using digraph-based method and solving a set of equations is also needed, which significantly slows down the algorithm of finding them.

4 Example

4.1 Class $\mathcal {K}_{1}$

Example 3

Let as consider the following example. For the given characteristic polynomial

$$\begin{aligned} d(z)=1-z^{-1}-z^{-2}-z^{-3} \end{aligned}$$

(5)

determine entries of the state matrix $\mathbf {A}$ using digraph theory.

Fig. 4

Monomials

In the first step we write the following initial conditions: number of colours in digraph: $colour:=1$; monomials: $M_{1}=z^{-1}$; $M_{2}=z^{-2}$; $M_{3}=z^{-3}$. For every simple monomial $M_{1}$, $M_{2}$ and $M_{3}$ we determine all possible realisations using digraph theory. On the Fig. 4a is presented digraph structure realisation of the monomial $M_{1}$; on Fig. 4b is presented digraph structure realisation of the monomial $M_{2}$ and on Fig. 4c is presented digraph structure realisation of the monomial $M_{3}$. In the next step using all combinations of the digraph monomial representations we determine all possible digraph structure, which satisfy characteristic polynomial (5). One of the possible digraph structures, which satisfies Condition $S_{1}$, is presented on Fig. 5.

Fig. 5

One-dimensional digraph corresponding to characteristic polynomial (5)

Finally, we write state matrices in the following form:

$$\begin{aligned} \mathbf {A}=\left[ \begin{array}{ccc} w(v_{1},v_{1})_{\mathfrak {A}} &{} w(v_{2},v_{1})_{\mathfrak {A}} &{} w(v_{3},v_{1})_{\mathfrak {A}}\\ w(v_{1},v_{2})_{\mathfrak {A}} &{} 0 &{} 0\\ 0 &{} w(v_{2},v_{3})_{\mathfrak {A}} &{} 0 \end{array}\right] \end{aligned}$$

(6)

4.2 Class $\mathcal {K}_{2}$

Example 4

Let as consider the following example. For the given characteristic polynomial

$$\begin{aligned} d(z_{1},z_{2})=1-z_{1}^{-2}z_{2}^{-1}-z_{1}^{-2}-z_{1}^{-1}z_{2}^{-1} \end{aligned}$$

(7)

determine entries of the state matrices $\mathbf {A}_{1}$ and $\mathbf {A}_{2}$ using digraph theory.

Fig. 6

A two-dimensional digraph $\mathfrak {D}^{(2)}$ structure corresponding to (7)

Solution. On Fig. 6 is presented digraph structure corresponding to the characteristic polynomial (7). Considered digraph consist from three digraphs (presented on Fig. 7), corresponding to monomials: $M_{1}=z_{1}^{-2}z_{2}^{-1}$ (see Fig. 7a); $M_{2}=z_{1}^{-2}$ (see Fig. 7b); $M_{3}=z_{1}^{-1}z_{2}^{-1}$ (see Fig. 7c).

Therefore investigated digraph does not belong to the class $S_{1}$ (as the condition ($S_{1_{a}}$) is not met). In digraph structure presented on Fig. 6 appears additional cycle presented on Fig. 8 and digraph structure belong to the class $S_{2}$ (as it has exactly one redundant cycle in the digraph). Additional cycle in digraph makes that in the characteristic polynomial appears additional monomial that should not be represented. The characteristic polynomial will have the following structure: $\widetilde{d}(z_{1},z_{2})=d(z_{1},z_{2})+z_{1}^{-1}z_{2}^{-2}$. In this class of digraph we can not determine arcs weights fulfilling the characteristic polynomial (7).

Fig. 7

Monomials

Fig. 8

Additional cycle in two-dimensional digraph structure

4.3 Class $\mathcal {K}_{3}$

Example 5

Let as consider the following example. For the given characteristic polynomial

$$\begin{aligned} d(z_{1},z_{2})=1-a_{1}z_{1}^{-2}-a_{2}z_{2}^{-2} \end{aligned}$$

(8)

determine entries of the state matrices $\mathbf {A}_{1}$ and $\mathbf {A}_{2}$ using digraph theory.

Fig. 9

A two-dimensional digraph $\mathfrak {D}^{(2)}$

Fig. 10

Monomials

Solution. On Fig. 9 is presented digraph structure corresponding to the characteristic polynomial (8). Considered digraph consist from four digraphs: two digraphs corresponding to the monomials $M_{1}$ (see Fig. 10a) and $M_{2}$ (see Fig. 10b) and two additional digraphs (see Fig. 10c, d) which generate additional monomials $M_{3}$ and $M_{4}$ that are not occurring in the characteristic polynomial (8). Therefore investigated digraph does not belong to the class $S_{1}$ (as the conditions ($S_{1_{a}}$) and ($S_{1_{b}}$) are not met) and does not belong to the class $S_{2}$ (as it has more than one redundant cycle in the graph).

Using digraph structure we have the following characteristic polynomial:

(9)

In this situation we have four possible variants:  

$V_{1}:$ :

In the first variant the following relations must be satisfied:

(10)

 

(a):

The cycles cancel each other. In this case the following relations must be satisfied:

(11)

If the conditions: (10) and (11) are met, then there exist a solution in the class $\mathcal {K}_{3}$.

(b):

The cycles do not cancel each other. In this case the following relations must be satisfied:

(12)

If the conditions: (10) and (12) are met, then there exist a solution in the class $\mathcal {K}_{2}$.

$V_{2}:$ :

In the second variant the following relations must be satisfied:

(13)

 

(a):

The cycles cancel each other. In this case the following relations must be satisfied:

(14)

If the conditions: (13) and (14) are met, then there exist a solution in the class $\mathcal {K}_{3}$.

(b):

The cycles do not cancel each other. In this case the following relations must be satisfied:

(15)

If the conditions: (13) and (15) are met, then there exist a solution in the class $\mathcal {K}_{2}$.

5 Concluding Remarks

In this paper there is introduced the first classification of digraph structures that are used to solve characteristic polynomials. Three classes of such structures are determined along with conditions how to classify digraph solutions obtained with parallel algorithm into each of classes. This allows to fully check the validity of solutions for given characteristic polynomial and determine if we want only solutions that can be obtained in fast and easier way using the algorithm (the ones in $\mathcal {K}_1$ class) or if we want to check all solutions, despite the need to solve a system of polynomial equations (adding solutions from $\mathcal {K}_3$ class). We can also determine that given digraph structure is invalid solution for given characteristic polynomial. Such basic classification is the first step for determination of properties of different digraph structures (like how can be check reachability and availability from digraph only, without need of system matrices) and introducing methods for finding best solutions fast.