Optimization Models
Home
Software
Links
Index
Contact
1. Introduction
1.1. Overview
1.2. Optimization Models
2. Linear Algebra
2.1. Vectors
2.2. Matrices
2.3. Linear Equations
2.4.  Least-Squares
2.5. Eigenvalues
2.6  Singular Values
3. Convex Models
3.1. Convexity
3.2. LP and QP
3.3. SOCP
3.4. Robust LP
3.5. GP
3.6. SDP
3.7. Non-Convex Models
4. Duality
4.1. Weak Duality
4.2. Strong Duality
4.3.  Applications
5. Case Studies
5.1. Senate Voting
5.2. Antenna Arrays
5.3. Localization
5.4. Circuit Design

Incidence matrix of a network

Matrices > Basics > Example

Mathematically speaking, a network is a graph of m nodes connected by n directed arcs. Here, we assume that arcs are ordered pairs, with at most one arc joining any two nodes; we also assume that there are no self-loops (arcs from a node to itself). We do not assume that the edges of the graph are weighted — they are all similar.

We can fully describe the network with the so-called arc-node incidence matrix, which is the m times n matrix defined as

A_{ij} = left{ begin{array}{ll} 1 & mbox{if arc } j mbox{ starts at node } i -1 & mbox{if arc } j mbox{ ends at node } i 0 & mbox{otherwise.} end{array} right. , ;; 1 le i le m, ;; 1 le j le n.
alt text 

The figure shows the graph associated with the arc-node incidence matrix

A = left[begin{array}{cccccccc} 1 & 1 & 0 & 0 & 0 & 0 & 0 & -1 -1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 0 & -1 & -1 & -1 & 1 & 1 & 0 & 0 0 & 0 & 0 & 1 & 0 & 0 & -1 & 0 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 0 & 0 & 0 & 0 & -1 & 0 & 0 & 0 end{array}right] .

See also: Network flow.