# Determining the Exponent of Oscillatory Matrices

## Introduction
A matrix $A\in\R^{n\times n}$ is called **oscillatory** if it is invertible and TN (I-TN) and there exists a postive integer $q$ such that $A^q$ is TP. The least positive integer $r=r(A)$ such that $A^r$ is TP is called the *exponent* of the oscillatory matrix $A$. Determining the exponent of an oscillatory matrix is an important task.

Oscillatory matrices admit Successive Elementary Bidiagonal (SEB) factorizations that are associated with planar networks. To show that $A^r$ is TP, for $A$ oscillatory, it is enough to show that all corner minors of $A^r$ are positive. Equivalently, it is enough to show that for each corner minor, at least one family of vertex-disjoint paths, connecting the minor's source and destination indexes, exists in the planar network associated with the SEB factorization of $A^r$.

Here, we implemented few tools that can be used to determine the exponent of an oscillatory matrix based on the families of vertex-disjoing paths. For more details on oscillatory matrices, SEB factorization and associated planar networks, please refer to the paper: [On the Exponent of Several Classes of Oscillatory Matrices](https://arxiv.org/abs/1910.10709).

## SEB Factorization and Planar Networks
Let $L_i(q)\in\R^{n\times n}$, $q\ge 0$, denote a matrix with $1$ along the diagonal, $q$ in entry $(i,i-1)$ and $0$ elsewhere, and let $U_i(q):=(L_i(q))^T$. $q$ is called the parameter of $L_i(q)$. Note that $L_i(0)=I$ for all $i$. Then an oscillatory matrix $A$ can be written as $A=LDU$, with (we omit the parameter values) $L=[L_n\cdots L_2]\cdots [L_n]$, $U=[U_n]\cdots [U_2\cdots U_n]$, and $D$ diagonal with positive diagonal entries. This is called the *SEB factorization* of the oscillatory matrix $A$.
For example, for $n=5$, an oscillatory matrix $A\in\R^{5\times 5}$ can be written as $A=LDU$ with
$$
\begin{equation}
L:=[L_5L_4L_3L_2][L_5L_4L_3][L_5L_4][L_5],
\label{eq:L}
\tag{1}
\end{equation}
$$
and
$$
\begin{equation}
U:=[U_5][U_4U_5][U_3U_4U_5][U_2U_3U_4U_5].
\label{eq:U}
\tag{2}
\end{equation}
$$

Associated with the SEB factorization is a *planar network*. Each $L_i(q)$ [$U_i(q)$] is described by a diagram consisting of a diagonal directed edge (with weight $q$) from index $i$ to index $i-1$ [from index $i-1$ to index $i$], and $n$ horizontal directed edges (with weight of $1$). The diagram corresponding to the matrix $D$ consists of $n$ horizontal directed edges with weights $d_{ii}$. The planar network associated with an SEB factorization is established by concatenating, in order, the diagrams corresponding to all $L_i$, $D$, and all the $U_i$ matrices.
The following planar network is associated with the SEB factorization given in $\eqref{eq:L}$ and $\eqref{eq:U}$:



Given an oscillatory matrix $A=LDU$, we implement the computation of the family of vertex-disjoint paths corresponding to all lower-left [upper-right] corner minors of $L$ [$U$]. The paths corresponding to $U$ are determined by computing the paths of all lower-left corner minors of $U^T$, and then converting them to the paths of all upper-right corner minors of $U$.
Specifically, for each lower-left corner minor, we compute the minimum number of copies of $A$ such that a family of vertex-disjoint paths can be realized. In addition, we display the corresponding family for each corner minor, for both $L$ and $U$.


We use a **triangle graph** that is derived from the planar network associated with the left-hand side of the SEB factorization of I-TN matrices to deduce the families of paths.

## Triangle Graph
A triangle graph consists of $n-1$ columns of cells ordered left to right. The first (left-most) column represents the product $[L_n\cdots L_2]$, the second column represents the product $[L_{n-1}\cdots L_2]$, and so on, where the last column represents $[L_n]$. In each column, the top cell represents the existence/absence of $L_n$ (in the product $[L_n\cdots L_2]$), that is, it represents the boolean value $\ell_n>0$, where $\ell_n$ is the parameter of $L_n$. The second-top cell represents the existence/absence of $L_{n-1}$, and so on, where the bottom cell represents the existence/absence of $L_{2}$. Similarly for the other columns. Thus, the first column contains $n-1$ cells, the second $n-2$ cells and so on, where the last column contains a single cell. 

We say that a triangle graph represents the *signature* of the left-hand side SEB factorization, that is, it represents $\ell_i>0$ rather than the value $\ell_i$ for all $i$. Thus, an oscillatory matrix $A=LDU$, is associated with two triangle graphs: one corresponding to $L$ and one to $U^T$.

The graph also contains indexes on the left and in the bottom. These represent the source and destination indexes, respectively, of a lower-left corner minor.
The indexes of a lower-left corner minor are denoted by $s|d$, where $s$ [$d$] denotes the source [destination] indexes. For example, the lower-left corner minor indexes for $n=5$ (excluding the determinant) are: 
1. $5|1$. In the context of paths along the triangle graph, this corresponds to a family of one path from the source index 5 to the destination index 1.
2. $4,5|1,2$. This corresponds to a family of two vertex-disjoint paths: a path from 4 to 1, and a path from 5 to 2.
3. $3,4,5|1,2,3$. This corresponds to a family of three vertex-disjoint paths: a path from 3 to 1, from 4 to 2, and from 5 to 3.
4. $2,3,4,5|1,2,3,4$. This corresponds to a family of four vertex-disjoint paths: a path from 2 to 1, a path from 3 to 2, a path from 4 to 3, and a path from 5 to 4.

Below is an example of a triangle graph for $n=5$. Here, "O" indicates the existence 
of the corresponding $L_i$ matrix, and "X" the absence. 
The first column in the triangle graph corresponds to $L_5L_4L_3L_2$, the second to $L_5L_4L_3$, 
the third to $L_5L_4$ and the last column to $L_5$. Recall that in each column in the graph, the top sign (i.e. "O" or "X") 
corresponds to $L_n$ in $[L_nL_{n-1}....L_i]$. 

The following triangle graph corresponds to $L=[L_5L_3L_2][L_5L_3][L_4][L_5]$:

***
                       5 O
                       4 X O
                       3 O X X
                       2 O O O O
                         1 2 3 4

***

This triangular graph corresponds to the left-hand side of the following planar network:




## Vertex-Disjoint Paths
A path in the triangle graph is defined by a sequence of 2D points along the graph. We 
start at a source index on the left, and move **either down or diagonally** along the graph. 
Moving diagonally in the triangle graph corresponds to a horizontal path in the planar network. 
Moving down in the graph corresponds to moving down along an edge in the planar network.

The flow along the cells in the triangle diagram is done as follows:
* At a "O" cell, we move down if we have yet to reach the destination index, otherwise we move diagonally.
* At a "X" cell, we move diagonally.

We stop once we reach the destination index.

The following figure displays the triangle graph given above with the possible flow from each node. That is, both diagonal and down-pointing edges emerge from a "O" cell, whereas only a diagonal edge emerges from a "X" cell.



A path in the triangle graph is represented by a list of 2D points (which are lists by themself
of two numbers: the y-axis value and the x-axis value). 
For example, the path that starts in the source index 5 (i.e. in the 2D point [5,1]) in the
graph above and ends in the destination index 3 (i.e. in the 2D point [1,3]) is:
 
 [[5,1],[4,1],[3,2],[2,3],[1,3]]. 

Note that in this case, this is the minimal destination index that the 
source index 5 ([5,1]) can reach in the graph. This path corresponds to the following steps:

1. Starting from [5,1] corresponds to starting in the cell that corresponds to the index 5 (the top cell of the first column). This cell contains an "O" sign.
2. Moving down to the "X" sign below it (i.e. to [4,1]) corresponds to using the diagonal edge in $L_5$ in the product $[L_5L_3L_2]$  (in the planar network).
3. Moving diagonally to the "X" sign in the second column (i.e. to [3,2]) corresponds to using an horizontal edge (in the planar network).
4. Moving diagonally to the "X" sign in the third column (i.e. to [2,3]) corresponds to using an horizontal edge (in the planar network).
5. Moving down to [1,3] corresponds to using the diagonal edge in $L_4$ in $[L_4]$. At that point we reached the destination index. 

Given a 2D point in the triangle graph $[q_y, q_x]$ the corresponding index in the planar network 
is $q_y+q_x-1$. Thus, the path above corresponds to the following path in the planar network:

  [5, 4, 4, 4, 3].

In cases where a destination can not be reached (for example, 
in the example above, the source [5,1] (i.e. index 5) can not reach the destination [1,1] (i.e. index 1)) an additional
"copy" of the triangle graph is used. This is repeated until a path is realized.

Consider the left corner minor indexes $5|1$ and the triangle diagram above. Since a path starting from the source index 5 can only terminate in the minimal destination index 3, which is larger than the required destination index 1, we say that in a single copy of the graph, index 5 can reach index 3. We then use another copy of the triangle graph, however this time we start from the source index 3. In this copy, the path is $[[3,1],[2,1],[1,1]]$, that is in the second copy of the graph index 3 can reach index 1. Thus, we require two copies of the graph for index 5 to reach index 1, and the corresponding path is represented as a list of two lists, the first is the path in the first copy and the second is the path in the second copy:

$$[ [[5,1],[4,1],[3,2],[2,3],[1,3]],  [[3,1],[2,1],[1,1]] ].$$

For a general lower-left corner minor indexes $n-x+1,\cdots, n|1,\dots,n$, ($x\in\{1,\dots,n-1\}$), we start by trying to realize a path from the smallest index, i.e. a path from $n-x+1$ to $1$. We then move to realizing a path from $n-x+2$ to $2$, etc. For a given source index, once a path is generated in a single copy of the triangle diagram (which doesn't necessarily terminates in the required destination index), the cells above the path's cells are marked by "X". This is done to insure that all paths are vertex-disjoint paths. However, when using a new copy of the triangle diagram, we revert back to the original diagram without the added "X" marks.


In the context an oscillatory matrix $A=LDU$, we use the triangle graph to compute the families of
vertex-disjoint paths corresponding to all lower-left corner minors of $L$ and $U^T$, and thus deduce
the exponent of $A$.


## Imports


```python
import numpy as np

import TpTnOsc.utils as tpf
import TpTnOsc.osc_exp as oscp 
```

## An example from the description section above
This is the example used above in the description section for $n=5$. 


```python
%matplotlib inline
import matplotlib.pyplot as plt
from IPython.display import display
''' Define the input which is a list of L_i with positive parameters.
Here, L_4 is missing from [L_5L_4L_3L_2], L_4 is missing from
[L_5L_4L_3], L_5 is missing from [L_5L_4] and L_5 is not missing from [L_5]
'''
mat_info = [[5,3,2], [5,3], [4], [5]]  
# -----------------------------------------------------------------------------
# create a triangle graph object
G_L = oscp.Trig_G(info=mat_info)
# display the triangle graph
print("Triangle graph corresponding to mat_info:")
G_L.show_me()
# can also draw the graph
print("A draw of the triangle graph:")
plt1, ax = plt.subplots(figsize=(8,8))
G_L.draw_me(ax, nd_offset=[0.2, 0.3])
ax.margins(.1, .1)    
display(plt1)
plt.close()
# check if it corresponds to a rhs of the SEB of an I-TN matrix
print(f"\nGraph correponds to rhs of I-TN matrix: {G_L.valid_ITN}")
# create a lower-left corner minor object based on the triangle graph object
LC = oscp.LLC_families(G_L, name='L')
# run the paths computation
LC.run(verbose=False)
# display paths and number of copies results
print('\nSource->Destination results (verbose):')
LC.display_results()
print('\nSource->Destination results (compressed):')
LC.display_results(compress=True)
```

## Another example of using Trig_G and LLC_families classes
Here, the input is a list of available $L_i$ matrices in each group in the left-hand side of the SEB factorization.


```python
''' Define the input which is a list of L_i with positive parameters.
Here, L_4 and L_3 are missing from [L_5L_4L_3L_2], L5 and L_4 are missing from
[L_5L_4L_3], L_5 is missing from [L_5L_4] and L_5 is not missing from [L_5]
'''
mat_info = [[5,2], [3], [4], [5]]  
# -----------------------------------------------------------------------------

# create a triangle graph object
G_L = oscp.Trig_G(info=mat_info)
# display the triangle graph
print("Triangle graph corresponding to mat_info:")
G_L.show_me()
# check if it corresponds to a rhs of the SEB of an I-TN matrix
print(f"\nGraph correponds to rhs of I-TN matrix: {G_L.valid_ITN}")
# create a lower-left corner minor object based on the triangle graph object
LC = oscp.LLC_families(G_L, name='Q')
# run the paths computation
LC.run(verbose=False)
# display paths and number of copies results
print('\nSource->Destination results:')
LC.display_results()
# can also display the reverse paths and number of copies results
print('\nDestination->Source results:')
LC.display_results(reverse=True)
# can also display raw results
#LC.display_raw_results()
print(f"\nMinimum number of copies to realize all lower-left corner minors = {LC.r}.")


```

    Triangle graph corresponding to mat_info:
     5 O 
     4 X X 
     3 X X X 
     2 O O O O 
       1 2 3 4 
    
    Graph correponds to rhs of I-TN matrix: True
    
    Source->Destination results:
    Q:
    	5|1 (3 copies):
    		[5->4->4->4->3][3->3->2][2->1]
    	4,5|1,2 (3 copies):
    		[4->4->4->3][3->3->2][2->1]
    		[5->5->5->5->4][4->4->4->3][3->3->2]
    	3,4,5|1,2,3 (2 copies):
    		[3->3->2][2->1]
    		[4->4->4->3][3->3->2]
    		[5->5->5->5->4][4->4->4->3]
    	2,3,4,5|1,2,3,4 (1 copies):
    		[2->1]
    		[3->3->2]
    		[4->4->4->3]
    		[5->5->5->5->4]
    Minimum number of copies to realize all families = 3.
    
    Destination->Source results:
    Q:
    	1|5 (3 copies):
    		[1->2][2->3->3][3->4->4->4->5]
    	1,2|4,5 (3 copies):
    		[2->3->3][3->4->4->4][4->5->5->5->5]
    		[1->2][2->3->3][3->4->4->4]
    	1,2,3|3,4,5 (2 copies):
    		[3->4->4->4][4->5->5->5->5]
    		[2->3->3][3->4->4->4]
    		[1->2][2->3->3]
    	1,2,3,4|2,3,4,5 (1 copies):
    		[4->5->5->5->5]
    		[3->4->4->4]
    		[2->3->3]
    		[1->2]
    Minimum number of copies to realize all families = 3.
    
    Minimum number of copies to realize all lower-left corner minors = 3.


## An example of using OSC_exp class
Here, the input is an oscillatory matrix.


```python
# define an oscillatory matrix
A = np.array([[3, 1, 0, 0], [1, 4, 1, 0.1], [0.1, 1, 5, 3], [0, 0, 2, 7]])            
# -----------------------------------------------------------------------------
print(f"A =\n{A}")
# check that this is indeed an oscillatory matrix
print(f"\nMatrix A is OSC: {tpf.is_osc_from_factorization(A)}")
try:
    osc_cls = oscp.OSC_exp(A) # create an OSC_exp object
except ValueError as ve:
    print(f"{ve}. Aborting...")
else:
    osc_cls.run()  # run it
    osc_cls.display_results()  # display its results
    # or can show paths corresponding to both lower-right and upper-right corner minors
    print('\nShowing paths for both lower-left and upper-right corner minors for both L and U^T:')
    osc_cls.display_results(show_also_reverse=True) 
finally:
    for k in osc_cls.G.keys():
        print(f'Triangle graph of {k}:')
        plt1, ax = plt.subplots(figsize=(8,8))
        osc_cls.G[k].draw_me(ax, nd_offset=[0.15, 0.2])
        ax.margins(.1, .1)    
        display(plt1)
        plt.close()
    print('Done.')

```

## Another example
Here, for $A=LDU$, we set $U=[U_2\cdots U_n]$ and $L = [L_n\cdots L_2][L_n\cdots L_3]\cdots[L_n]$,
that is, $L$ consists of all $L_i$ matrices in the right-hand side of the SEB factorization, and
$U$ consists of only the last group in the right-hand factorization. It is known that 
in this case, $r(A)=n-1$.


```python
n = 8  # set n value
# --------------------------------------------------------------------------------------------
k = tpf.EB_factorization_n2k(n)
valsl = np.ones(k)
valsd = np.ones(n)
valsu = np.r_[np.ones(n-1), np.zeros(k-(n-1))]
A = tpf.compute_matrix_from_EB_factorization(valsl, valsd, valsu)
print(f"A =\n{A}")
# check that this is indeed an oscillatory matrix
print(f"\nMatrix A is OSC: {tpf.is_osc_from_factorization(A)}")
try:
    #osc_cls = OSC_exp(A) # create an OSC_exp object
    osc_cls = oscp.OSC_exp.from_vals_ldu(valsl, valsd, valsu) # can also create from the SEB factorization
except ValueError as ve:
    print(f"{ve}. Aborting...")
else:
    osc_cls.run()  # run it
    osc_cls.display_results(compress=True)  # display its results
finally:
    for k in osc_cls.G.keys():
        print(f'Triangle graph of {k}:')
        plt1, ax = plt.subplots(figsize=(10,10))
        osc_cls.G[k].draw_me(ax, nd_offset=[0.3, 0.4])
        ax.margins(.1, .1)    
        display(plt1)
        plt.close()
    print('Done.')

```

6c1d65ce9beb334951b500666362a3e73f6680d2
ipynb
Jupyter Notebook
examples/osc_exp_examples.ipynb
yoramzarai/TpTnOsc
f1fdd1a0ebc7d64177f4281bf3be5f2665fdcf90
MIT
examples/osc_exp_examples.ipynb
yoramzarai/TpTnOsc
f1fdd1a0ebc7d64177f4281bf3be5f2665fdcf90
MIT
examples/osc_exp_examples.ipynb
yoramzarai/TpTnOsc
f1fdd1a0ebc7d64177f4281bf3be5f2665fdcf90
MIT
Qwen/Qwen-72B
1. YES
2. YES