----- > [!proposition] Proposition. ([[directed acyclic network has upper triangular adjacency matrix wrt vertical ordering]]) > Let $G$ be a [[network|directed]] [[acyclic network]]; give it the [[vertically ordering acyclic networks|vertical ordering]]. Then the [[adjacency matrix]] of $G$ is (strictly) [[upper-triangular matrix|upper-triangular]]. > [!basicexample] > ![[CleanShot 2023-09-14 at 17.23.59@2x 1.jpg]] > The above [[network]] has [[adjacency matrix]] $\begin{bmatrix} \textcolor{gray}{0} & \textcolor{lightgray}{0} & \textcolor{white}{1} & \textcolor{lightgray}{0} & \textcolor{white}{1} & \textcolor{lightgray}{0} & \textcolor{lightgray}{0} & \textcolor{lightgray}{0} & \textcolor{lightgray}{0} \\ \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{white}{1} & \textcolor{lightgray}{0} & \textcolor{lightgray}{0} & \textcolor{white}{1} & \textcolor{lightgray}{0} & \textcolor{lightgray}{0} & \textcolor{lightgray}{0} \\ \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{lightgray}{0} & \textcolor{lightgray}{0} & \textcolor{white}{1} & \textcolor{lightgray}{0} & \textcolor{lightgray}{0} & \textcolor{lightgray}{0} \\ \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{white}{1} & \textcolor{lightgray}{0} & \textcolor{lightgray}{0} & \textcolor{white}{1} & \textcolor{lightgray}{0} \\ \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{lightgray}{0} & \textcolor{white}{1} & \textcolor{lightgray}{0} & \textcolor{white}{1} \\ \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{white}{1} & \textcolor{lightgray}{0} & \textcolor{lightgray}{0} \\ \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{white}{1} & \textcolor{white}{1} \\ \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{lightgray}{0} \\ \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0} & \textcolor{gray}{0}. \end{bmatrix}$ > [!proof]- Proof. ([[directed acyclic network has upper triangular adjacency matrix wrt vertical ordering]]) > Recall that entry $ij$ of an [[adjacency matrix]] is $1$ iff node $j$ has an outgoing edge to node $i$. Because the [[vertically ordering acyclic networks|vertical ordering dictates]] each node of $G$ has outgoing edges exclusively to nodes of lower index, it is not possible for entry $ij$ of $A(G)$ to be $1$ whenever $i>j$. ----- #### ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```