Tree Data Structures and Matrix Inversion

Linear Algebra: Matrix Inversion following Adjoint Method

  • Target Equation: The final goal is to verify that A×A−1=IA \times A^{-1} = I, where II is the Identity Matrix.

  • Given Matrix AA:   \n  A = \begin{pmatrix}\n  4 & -2 & 1 \\\n  9 & 6 & 5 \\\n  7 & -3 & 8\n  \end{pmatrix}\n  

  • Cofactor Calculations (aija_{ij}):   - a11=(−1)2∣65−38∣=(48−(−15))=63a_{11} = (-1)^2 \begin{vmatrix} 6 & 5 \\ -3 & 8 \end{vmatrix} = (48 - (-15)) = 63   - a12=(−1)3∣9578∣=−(72−35)=−37a_{12} = (-1)^3 \begin{vmatrix} 9 & 5 \\ 7 & 8 \end{vmatrix} = -(72 - 35) = -37   - a13=(−1)4∣967−3∣=(−27−42)=−69a_{13} = (-1)^4 \begin{vmatrix} 9 & 6 \\ 7 & -3 \end{vmatrix} = (-27 - 42) = -69   - a21=(−1)3∣−21−38∣=−(−16−(−3))=13a_{21} = (-1)^3 \begin{vmatrix} -2 & 1 \\ -3 & 8 \end{vmatrix} = -(-16 - (-3)) = 13   - a22=(−1)4∣4178∣=(32−7)=25a_{22} = (-1)^4 \begin{vmatrix} 4 & 1 \\ 7 & 8 \end{vmatrix} = (32 - 7) = 25   - a23=(−1)5∣4−27−3∣=−(−12−(−14))=−2a_{23} = (-1)^5 \begin{vmatrix} 4 & -2 \\ 7 & -3 \end{vmatrix} = -(-12 - (-14)) = -2   - a31=(−1)4∣−2165∣=(−10−6)=−16a_{31} = (-1)^4 \begin{vmatrix} -2 & 1 \\ 6 & 5 \end{vmatrix} = (-10 - 6) = -16   - a32=(−1)5∣4195∣=−(20−9)=−11a_{32} = (-1)^5 \begin{vmatrix} 4 & 1 \\ 9 & 5 \end{vmatrix} = -(20 - 9) = -11   - a33=(−1)6∣4−296∣=(24−(−18))=42a_{33} = (-1)^6 \begin{vmatrix} 4 & -2 \\ 9 & 6 \end{vmatrix} = (24 - (-18)) = 42

  • Adjoint of Matrix AA (AdjAAdj A):   - The Adjoint matrix is the transpose of the cofactor matrix.   \n  Adj A = \begin{pmatrix}\n  63 & 13 & -16 \\\n  -37 & 25 & -11 \\\n  -69 & -2 & 42\n  \end{pmatrix}\n  

  • Determinant calculation (∣A∣|A|):   - ∣A∣=4(63)−(−2)(37)+1(−69)|A| = 4(63) - (-2)(37) + 1(-69)   - ∣A∣=252+74−69=257|A| = 252 + 74 - 69 = 257

  • Inverse of Matrix AA (A−1A^{-1}):   - Formula: A−1=1∣A∣AdjAA^{-1} = \frac{1}{|A|} Adj A   - A−1=1257(6313−16−3725−11−69−242)A^{-1} = \frac{1}{257} \begin{pmatrix} 63 & 13 & -16 \\ -37 & 25 & -11 \\ -69 & -2 & 42 \end{pmatrix}

  • Verification Process (A⋅A−1=IA \cdot A^{-1} = I):   - Applying matrix multiplication and dividing by the determinant result in the following values (approximate):     \n    A^{-1} \approx \begin{pmatrix} 0.245 & 0.050 & -0.062 \\ -0.143 & 0.097 & -0.042 \\ -0.268 & -7.782 & 0.163 \end{pmatrix}\n       - When calculating A×A−1A \times A^{-1}, the result converges to the Identity matrix II.

Data Structures: Tree Terminology

  • Core Components:   - Root Node: The top-most unique node in the tree from which all other nodes originate.   - Total Nodes (nn): The absolute count of all elements in the tree.   - Edge: The connection/path between two nodes. Total edges = n−1n - 1.

  • Positional Roles:   - Parent Node: A node that has branches leading to other nodes.   - Child Node: A node that has an incoming connection from a parent.   - Internal Nodes: Nodes that have at least one child.   - Leaf Node (External Node): A node that has no children.   - Siblings: Nodes that share the same parent node.

  • Structural Metrics:   - Degree of a Node: The total number of children a specific node has.   - Degree of a Tree: The maximum degree found among all nodes in that tree.   - Level: The distance from the root. The root is typically at Level 0.   - Height of a Tree: The maximum level found in the tree (the longest path from root to leaf).   - Depth of a Tree: Equivalent to the height of the tree.   - Ancestor: Any node on the path from the root to a specific node.   - Descendant: Any node reachable by moving down from a specific node.

Analysis of Specific Tree Examples

Example 1 (Numeric Tree with 16 Nodes)

  • Root Node: 1

  • Total Nodes: 16

  • Edges: 16−1=1516 - 1 = 15

  • Parent Nodes: 1, 2, 3, 4, 5, 7, 8, 10, 12

  • Child Nodes: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

  • Internal Nodes: 1, 2, 3, 4, 5, 7, 8, 10, 12

  • Leaf Nodes: 9, 14, 15, 6, 11, 13, 16

  • Siblings: (2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15)

  • Degree of Tree: 3

  • Height of Tree: 4

  • Level of Tree: 0, 1, 2, 3, 4

  • Depth of Tree: 4

  • Subtrees Examples:   - SA=2,1SA = 2, 1   - SD=6,7,8,11,12,13,16SD = 6, 7, 8, 11, 12, 13, 16

Example 2 (Lettered Tree with 11 Nodes)

  • Root Node: A

  • Total Nodes: 11

  • Edges: 10

  • Parent Nodes: A, B, C, E, G

  • Child Nodes: B, C, D, E, F, G, H, I, J, K

  • Internal Nodes: A, B, C, E, G

  • Leaf Nodes: D, F, I, J, H, K

  • Siblings: (B, C), (D, E, F), (G, H), (I, J)

  • Degree of Tree: 3 (Node B has three children: D, E, F)

  • Height of Tree: 3

Binary Trees

  • Definition: A tree structure where every node has at most two children. The number of child nodes can be within the range of 0, 1, or 2.

  • Full Binary Tree: A tree where every node has either zero children (leaf) or exactly two children.

  • Insertion Logic:   - The first node inserted becomes the Root.   - Subsequent nodes are inserted as Left Child first, then Right Child (depending on the specific binary tree logic such as BST).

Questions & Discussion

  • Q: What is the sibling of Node A in the second example?   - A: None (Node A is the root).

  • Q: What is the degree of Node A in the lettered tree?   - A: 2 (Children: B and C).

  • Q: What is the height of a leaf node?   - A: The height of a leaf node is always 0.

  • Q: What is the level of the tree if the height is 3?   - A: levels 0, 1, 2, 3.

  • Q: Identify the descendants of Node B in the lettered tree.   - A: D, E, F, I, J.

  • Q: Identify the ancestors of Node I.   - A: E, B, A.