## Posts Tagged ‘**Eigen Decomposition**’

## Water and Wine Problem

Take two containers, and . Initially, is full of water and is full of wine. Remove a teaspoon of water from and put it in , then a teaspoon of the mixture in and put it in . In what proportions are the water and wine now mixed in and ? What are the proportions of water and wine in each container after iterations?

First some assumptions: containers and are identical in volume and both capable of containing the combined fluid of each. The initial amount of fluid in each container is identical. When transferring fluids between the containers, none of the fluid is lost. Rather than focusing on what amount a teaspoon represents, we’ll state that we are going to transfer a percentage, , of to . Likewise, when transferring fluid from to , we’ll use a percentage . Note that the amount that is transferred, , from to has to be equal to the amount that is later transferred, , from to . From that fact we can conclude that . Following these conventions, we arrive at the following formulated events in the problem statement:

Container A | Container B | |||

Water | Wine | Water | Wine | |

Initially, A is full of water and B is full of wine. | ||||

Remove a teaspoon of water from A and put it in B, | ||||

then a teaspoon of the mixture in B and put it in A. |

One way of capturing these events is to model the system, , as a matrix. Each row of a matrix represents a container and each column of the matrix represents the amount of water or wine in the container. The initial state of the system, , is the amount of water and wine in each container. The act of transferring fluid from one container to another and back again is given by which simplifies to . To determine the quantities of water and wine in each container after iterations, we can looks at the recurrence relation which simplifies to .

To figure out a closed form solution to we’ll note that the system is a system of difference equations. The general solution being where is a coefficient based on initial conditions, is the i’th eigenvector and is the i’th eigenvalue, i.e., the i’th solution to .

Following this practice, we arrive at . To find and we solve for and . We go with because it represents a container starting with one type of fluid and none of the other. The solution is . Important to note that the solution represents both containers and one can swap the water and wine labels.

One last thing of interest is to look at the limiting behavior of . As increases, the first term remains constant and the second term tends towards zero given the domain of . Thus, . Thus, no mater what size scope we take, we’ll always arrive at a container containing equal parts water and wine.

An alternative approach to figuring out the limiting behavior is to look directly at . Matrix computations are time consuming, so we’ll want to have a way to compute that minimizes the number of computations. One way to do this is to apply an Eigen Decomposition of a matrix. The idea is that we can decompose a matrix into a product of three matrices: first is the eigenvectors of the matrix, the second has the matrix’s eigenvalues along the diagonal and the third is an inverse of the first. The decomposition looks like the following: with . One important consequence is that we can compute easily now by and as a direct consequence of how is defined, .

Given that knowledge, we can decompose .

Taking the limit leads to the steady state solution of .