Linear Algebra | Antimatroid, The

Archive for the ‘Linear Algebra’ Category

Water and Wine Problem

Take two containers, $A$ and $B$ . 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$ . In what proportions are the water and wine now mixed in $A$ and $B$ ? What are the proportions of water and wine in each container after $n$ iterations?

First some assumptions: containers $A$ and $B$ 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, $\alpha$ , of $A$ to $B$ . Likewise, when transferring fluid from $B$ to $A$ , we’ll use a percentage $\beta$ . Note that the amount that is transferred, $\alpha \in (0, 1]$ , from $A$ to $B$ has to be equal to the amount that is later transferred, $\beta(\alpha + 1)$ , from $B$ to $A$ . From that fact we can conclude that $\beta = \frac{\alpha}{\alpha + 1}$ . 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.	$1$	$0$	$0$	$1$
Remove a teaspoon of water from A and put it in B,	$1-\alpha$	$0$	$\alpha$	$1$
then a teaspoon of the mixture in B and put it in A.	$1 - \alpha + \alpha \frac{\alpha}{\alpha+1}$	$\frac{\alpha}{\alpha+1}$	$\alpha(1-\frac{\alpha}{\alpha+1})$	$1-\frac{\alpha}{\alpha+1}$

One way of capturing these events is to model the system, $\mathcal{S}$ , 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, $\mathcal{S}_{0} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ , 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 $\mathcal{T} = \begin{pmatrix} 1 & \frac{\alpha}{\alpha+1} \\ 0 & \frac{1}{\alpha+1} \end{pmatrix} \begin{pmatrix} 1-\alpha & 0 \\ \alpha & 1 \end{pmatrix}$ which simplifies to $\frac{1}{\alpha+1} \begin{pmatrix} 1 & \alpha \\ \alpha & 1 \end{pmatrix}$ . To determine the quantities of water and wine in each container after $n$ iterations, we can looks at the recurrence relation $\mathcal{S}_{n} = \mathcal{T} \mathcal{S}_{n-1}$ which simplifies to $\mathcal{S}_{n} = \mathcal{T}^{n}\mathcal{S}_{0}$ .

To figure out a closed form solution to $\mathcal{S}_{n}$ we’ll note that the system is a system of difference equations. The general solution being $f(n) = \sum{ c_{i} \mathcal{Q}_{(i)} \lambda_{i}^n }$ where $c_{i}$ is a coefficient based on initial conditions, $\mathcal{Q}_{(i)}$ is the i’th eigenvector and $\lambda_{i}$ is the i’th eigenvalue, i.e., the i’th solution to $\lvert \mathcal{A} - \lambda \mathcal{I} \rvert = 0$ .

Following this practice, we arrive at $f(n) = \displaystyle c_{1} \begin{pmatrix} 1 \\ 1 \end{pmatrix} 1^{n} + c_{2} \begin{pmatrix} -1 \\ 1 \end{pmatrix} \frac{1-\alpha}{1+\alpha}^n$ . To find $c_{1}$ and $c_{2}$ we solve for $n = 0$ and $\displaystyle c_{1} \begin{pmatrix} 1 \\ 1 \end{pmatrix} + c_{2} \begin{pmatrix} -1 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$ . We go with $\begin{pmatrix} 1 \\ 0 \end{pmatrix}$ because it represents a container starting with one type of fluid and none of the other. The solution is $\displaystyle f(n) = \frac{1}{2} \begin{pmatrix} 1 \\ 1 \end{pmatrix} - \frac{1}{2} \begin{pmatrix} -1 \\ 1 \end{pmatrix} \frac{1-\alpha}{1+\alpha}^n$ . 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 $f(n)$ . As $n$ increases, the first term remains constant and the second term tends towards zero given the domain of $\alpha$ . Thus, $\displaystyle \lim_{n \to \infty} f(n) = \frac{1}{2} \begin{pmatrix} 1 \\ 1 \end{pmatrix}$ . 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 $\mathcal{S}_{n}$ . Matrix computations are time consuming, so we’ll want to have a way to compute $\mathcal{S}_{n}$ 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: $\mathcal{A} = \mathcal{Q} \Lambda \mathcal{Q}^{-}$ with $\Lambda_{i,i} = \lambda_{i}$ . One important consequence is that we can compute $\mathcal{A}^{n}$ easily now by $\mathcal{Q} \Lambda \mathcal{Q}^{-} \mathcal{Q} \Lambda \mathcal{Q}^{-} \cdots \mathcal{Q} \Lambda \mathcal{Q}^{-} = \mathcal{Q} \Lambda^n \mathcal{Q}^{-}$ and as a direct consequence of how $\Lambda$ is defined, $\Lambda^{n}_{i,i} = \lambda_{i}^{n}$ .

Given that knowledge, we can decompose $\mathcal{T}^{n} = \mathcal{Q}\Lambda^n\mathcal{Q}^{-} = \frac{1}{2} \begin{pmatrix} 1 & -1 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & \frac{1-\alpha}{1+\alpha}^{n} \end{pmatrix} \begin{pmatrix} 1 & 1 \\ -1 & 1 \end{pmatrix}$ .

Taking the limit $\displaystyle \lim_{n \rightarrow \infty} \mathcal{T}^n = \frac{1}{2} \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$ leads to the steady state solution of $\mathcal{S}_{\infty} = \frac{1}{2} \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$ .

Antimatroid, The

Archive for the ‘Linear Algebra’ Category

Water and Wine Problem

Pages

Follow by Email

Follow by RSS

Categories

Archives

Meta