Determining the human owners of stocks Consider a simple model of corporate ownership.
A corporation's ownership is split into shares. Each share can belong to either a person or another corporation. If a corporation owns shares in another corporation, the ownership of those shares is split between the owning corporation's owners (for example, if Citi owns GM shares, then those shares really belong to Citi's owners, some of which may be corporations). There may be cycles—Citi owns shares of GM which owns shares of Citi.
Is it possible to determine all of the human owners of a company, direct or indirect, and how much of the company each of them owns? Can you do this for all companies at once? What sort of algorithms would you use to do it?
(I don't have a strong mathematical background, but I am a programmer, so I'm familiar with graph theory. This looks like a weighted directed graph to me, but I don't know if that's where the solution lies. Feel free to add appropriate tags!)
 A: A weighted directed graph is a reasonable way to express the input of the problem, but that in itself doesn't tell us much about what to do with that graph.
Let's try to solve a basic variant:

Given a graph of inter-corporation ownership fractions, if I own a $p$% share of corporation $A$, how large a total share of corporation $B$ does that yield me? Here, "total" means "indirect" if $B\ne A$, and "direct plus indirect" when $B=A$.

It should be clear that the answer must be proportional to $p$, so let's write the answer as $\frac{p}{100}x_{AB}$, where $x_{AB}$ is an unknown coefficient that we'll try to compute.
Let's write $g_{AB}$ for "the fraction of $B$'s shares owned by corporation $A$". These coefficients are known inputs to the problem (you may recognize them as the elements of the incidence matrix for the ownership graph). Also, for definiteness in the example, we'll suppose that there are only 3 corporations, $A$, $B$ and $C$, in the world. It should be clear how to generalize to larger graphs.
Now, owning a share if $A$ is (for the purposes of the simplified problem, if not in economic reality) equivalent to owning that fraction of $A$'s stock in other companies (or itself):
$$ x_{AB} = g_{AA}x_{AB} + g_{AB}x_{BB} + g_{AC}x_{CB} $$
We see that investigating $x_{AB}$ leads us to consider $x_{BB}$ and $x_{CB}$, so let's write the corresponding equations for those:
$$ x_{BB} = g_{BA}x_{AB} + g_{BB}x_{BB} + g_{BC}x_{CB} + 1 $$
$$ x_{CB} = g_{CA}x_{AB} + g_{CB}x_{BB} + g_{CC}x_{CB} $$
The final $1$ in the equation for $x_{BB}$ represents the direct ownership of $B$ we get by owning $B$ shares.
What we have now is a linear equation system in three unknowns. Such systems are the domain of linear algebra, and have standard methods of solution. The one taught in introductory linear algebra is Gaussian elimination; there are various refinements for computer implementations that aim at reducing the precision loss entailed by floating-point arithmetic. For this particular problem it is probably the case that most corporations don't own stock in most other corporations, so our equation system is sparse, and there are special algorithms optimized for that case.
It is possible for a linear equation system to have either no solutions or multiple solutions. The no-solution case shouldn't arise here, as long as the input is not crazy (i.e., no negative ownership fractions, and the total fraction of each corporation owned by other corporations cannot exceed 100%). The multiple-solution case will happen if there's a group of corporations that together own each other 100% with no outside owners at all -- but it is easy to recognize such self-owning groups in advance and exclude them from the computation by standard graph algorithms (only consider corporations that are reachable in the graph from some known human owner).
To summarize, it turned out that in order to find how much of $B$ a share in $A$ implies, we naturally also found answers to how much of $B$ you get from a share in any corporation. So if all you're eventually interested in is the non-stock assets of $B$, you can do the computation once and multiply the $x_{\_B}$s by your portfolio.
On the other hand, if what you're interested in is not "who owns how much of $B$?", but "how much of everything do I own?", the above strategy would require you to do the whole computation with slightly different equations for each corporation. In that case you'd be better off using a different set of equations with variables $y_A$, $y_B$ and $y_C$ representing the total fractions of each company you own, and the equations:
$$\begin{align}y_A &= g_{AA}y_A + g_{AB}y_B + g_{AC}y_C + \tfrac{p_A}{100}\\
y_B &= g_{BA}y_A + g_{BB}y_B + g_{BC}y_C + \tfrac{p_B}{100}\\
y_C &= g_{CA}y_A + g_{CB}y_B + g_{CC}y_C + \tfrac{p_C}{100}\end{align}$$
where $p_A$ is the percentage of $A$ you own directly, and so forth.
The result of this alternative computation is the same as the one using the $x_{PQ}$s, which can be seen by a slight bit of additional linear algebra. It turns out that the $x_{PQ}$ unknowns just happen to be the elements of the inverse matrix of $I-(g_{ij})$. This gives a relation between the results of the first and second methods, say,
$$ y_B = x_{AB}\tfrac{p_A}{100} + x_{BB}\tfrac{p_B}{100} + x_{CB}\tfrac{p_C}{100} $$
So to get all answers in one computation, you could invert $I-(g_{ij})$ once and for all; there are standard methods for this too. Whether this is an efficient method depends on how sparse the ownership graph is, however.
