Archive for the ‘Linear Algebra’ Category
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
.