Derivative of product rule and functional equation

Consider the famous derivative of product rule:

$$ D(xy) = D(x) y + x D(y) $$ Is there a function that has an analogous functional equation? $$ f(xy) = f(x) y + x f(y) $$

Symmetric and Anti-symmetric Components

 

During various times in my math studies, I came across the following very similar looking equations.
For any complex number \(z\), we can split it into a symmetric and antisymmetric part: \[ \begin{align*} z & =\underbrace{\frac{z+\bar{z}}{2}}_{=:z_{1}}+\underbrace{\frac{z-\bar{z}}{2}}_{=:z_{2}}\\ \bar{z}_{1} & =z_{1}\\ \bar{z}_{2} & =-z_{2} \end{align*} \] For any square matrix \(A\), we can split it into a symmetric and antisymmetric part: \[ \begin{align*} A & =\underbrace{\frac{A+A^{T}}{2}}_{=:A_{1}}+\underbrace{\frac{A-A^{T}}{2}}_{=:A_{2}}\\ A_{1}^{T} & =A_{1}\\ A_{2}^{T} & =-A_{2} \end{align*} \] For any polynomial \(f\), we can split it into an odd and even part: \[ \begin{align*} f(x) & =\underbrace{\frac{f(x)+f(-x)}{2}}_{=:f_{1}(x)}+\underbrace{\frac{f(x)-f(-x)}{2}}_{=:f_{2}(x)}\\ f_{1}(-x) & =f_{1}(x)\\ f_{2}(-x) & =-f_{2}(x) \end{align*} \]
This prompts us to ask ourselves, is there a generalization of this?

Consider a vectorspace \(V\). Let \(g:V\rightarrow V\) be a function such that \[ \begin{align*} g(x_{1}+x_{2}) & =g(x_{1})+g(x_{2})\qquad(\text{linearity})\\ g(cx) & =cg(x)\qquad\qquad(\text{linearity})\\ g^{2}(x) & =x \end{align*} \] Then, given any \(x\in V\), it can be split into a \(g\)-symmetric and \(g\)-antisymmetric component as follows: \[ x=\underbrace{\frac{x+g(x)}{2}}_{=:x_{1}}+\underbrace{\frac{x-g(x)}{2}}_{=:x_{2}} \] We can verify that \[ \begin{align*} g(x_{1}) & =g\left(\frac{x+g(x)}{2}\right)=\frac{g(x)+g^{2}(x)}{2}=\frac{g(x)+x}{2}=x_{1}\\ g(x_{2}) & =g\left(\frac{x-g(x)}{2}\right)=\frac{g(x)-g^{2}(x)}{2}=\frac{g(x)-x}{2}=-x_{2} \end{align*} \] Not only that, this decomposition is unique. If not, let \[ x=x_{S}+x_{A}=\tilde{x}_{S}+\tilde{x}_{A} \] be two such representations. Then \[ 0=\underbrace{(x_{S}-\tilde{x}_{S})}_{=:y_{S}}+\underbrace{(x_{A}-\tilde{x}_{A})}_{=:y_{A}} \] Note that \[ \begin{align*} g(y_{S}) & =g(x_{S}-\tilde{x}_{S})=g(x_{S})-g(\tilde{x}_{S})=x_{s}-\tilde{x}_{S}=y_{S}\\ g(y_{A}) & =g(x_{A}-\tilde{x}_{A})=g(x_{A})-g(\tilde{x}_{A})=-x_{A}+\tilde{x}_{A}=-y_{A} \end{align*} \] Thus, \(y_{S}\) is \(g\)-symmetric and \(y_{A}\) is \(g\)-antisymmetric.

Now we have \[ \begin{align*} 0 & =y_{S}+y_{A}\\ \implies0=g(0) & =g(y_{S})+g(y_{A})\\ 0 & =y_{s}-y_{A} \end{align*} \] The first and third equations above imply \[ y_{A}=0 \] and hence \[ y_{S}=0 \] Thus \[ \begin{align*} x_{S} & =\tilde{x}_{S}\\ x_{A} & =\tilde{x}_{A} \end{align*} \] and the representation is unique.

Eigenvalues of a unitary matrix

Let b be a nonzero vector (from R^n).  Then, bb' is  an n x n matrix.

What are its eigenvectors and eigenvalues?

From linear algebra, we know that bb' is a rank one matrix. So it has one non-zero eigenvalue. The other n - 1 eigenvalues are all 0. 

Now that is the non-zero eigenvalue? Is it positive or negative? What is the associated eigenvector?

What about the eigenvectors corresponding to the zero eigenvalue?

Recall that the eigenvector of a matrix M is defined as any vector x such that 

M x = p x 


where p is the eigenvalue corresponding to x.

Since the matrix was formed with b alone, one would guess that the eigenvector and eigenvalue is somehow related to b. Let us try b.

Now, 

(bb') b = b (b'b) = (b'b) b

We use associativity of matrix multiplication above. In the last step, we could move the b'b to the front since it is a real number.

Thus b is indeed the eigenvector we are looking for with the eigenvalue b'b. Note that b'b is the length square of the vector b. Thus it is non-negative. 

What about the other eigenvectors with 0 eigenvalues?

Let c be a vector from the orthogonal complement of b. Then, b'c = 0. 

Thus, (bb') c = b (b'c) = b 0 = 0 = 0 c

Thus any vector orthogonal to b is an eigenvector of bb' with eigenvalue 0. 

As we know from linear algebra, the dimension of the orthongonal complement of b is n - 1, so we can find n-1 linearly independent vectors c such that (bb') c = 0. 

Thus we have all the eigenvalues and eigenvectors of bb'. 

Tailpiece:

As a next step, let b and c be two vectors from R^n. Form the matrix 

M = bb' + cc'

1. Is this always a rank 2 matrix?

2. What are the eigenvalues and eigenvectors of M in terms of b and c?
 

Apple Delivery

Here is a problem that I came across recently (from here):

The distance between the towns A and B is 1000 miles. There are 3000 apples in A, and the apples have to be delivered to B. The available car can take 1000 apples at most. The car driver has developed an addiction to apples: when he has apples aboard he eats 1 apple with each mile made. Figure out the strategy that yields the largest amount of apples to be delivered to B.

Now, there are two or three interesting ways to solve this problem.

The sure shot way is to use dynamic programming. We define the value function as

U(n,d) = the maximum number of apples that can be delivered to a distance d starting from an initial amount of n apples (under the conditions of the problem)

V(n,d) = the maximum of apples that can be delivered to a distance d starting from an initial amount of n apples if there are no intermediate stops

First, we derive an expression for V(n,d). Let c be the capacity of the car (in our case 1000). We have:

V(n,d) = 0, if d > c (you cannot go farther than c in single run)
= Max(n - d , 0), if n < c
= Floor(n/c) (c - d) + Max ( n mod c - d, 0)

Now the Bellman equation for U(n,d) can be written as:

U(n,d) = max_{1<= u <= d} U( V (n, u), d - u)

With the termination condition

U(n,0) = n (there is no transportation needed, thus no apple loss)

We can now program this DP and solve the problem to get the solution:

U(3000, 1000) = 833

But, is there a simpler way?

I could think of two arguments.

First we can use a greedy approach. Talking in monetary terms, our initial wealth is 1000 apples and the cost of transporting the apple is 1 apple/mile.

Consider the initial simplistic guess of transporting 3000 apples in 3 batches in one go. In each batch the number of apples transported is 1000, the average cost per apple is 1 apple per apple moved thus the total cost is 1000 x 1 = 1000. Thus we end up with 0 apples on the other end.

But is there a way we can decrease the average cost of transporting the apples so that at the end we have a positive balance?

The answer turns out to be yes. Consider moving 1000 apples by just one mile. The cost is 1 apple and the average cost per apple is 1/1000 much smaller than the 1 per apple cost we had earlier. (Of course, this is the cost for just one mile whereas earlier we had moved the apples a 1000 miles). But this gives the idea that if we follow a greedy approach and move the apples one mile at a time, the average cost per apple will be the lowest possible.

In fact, this approach works and we can easily write out a recursion for computing the number of apples left.

Let N(d) = the number of apples we have in the dth mile.

We have:

N(0) = 3000
N(d) = N(d-1) - Ceiling(N(d-1)/c)

Solving this recurrence forward gives us the answer N(1000) = 833.
In fact, if we recheck the solution to our DP, it will indeed show that the optimal solution has the corresponding N(d) values given by the above recurrence.

Now when we see a recurrence, usually there is a differential equation lurking around. It turns out to be the case here also.

Note that for small c (compared to N(d)), the above recurrence can be approximated as

N(0) = 3000
N(d) = N(d-1) - N(d-1)/c

Passing into infinitesimals, we have

N(0) = 3000
dN(x)/dx = - N(x)/c

We immediately get the solution as

N(x) = N(0) Exp(-x/c)

In our case, we get N(1000) = 1103.64.

Of course, we are off by about 32.5%, but note that N(0)/c = 3, which is not really large, so our approximation is also not that valid.

But if we had N(0) = 30000, say, we would get N(1000) = 11036.4 whereas the accurate solution from the difference equation (or the DP) is 10720, giving us an error of only about 3% - which is not bad compared to the effort involved in solving the DP.

Tailpiece:

We can also invert the problem and compute the farthest distance that you can go with the initial number of apples. For our original problem with 3000 apples, the answer turns out to be 1833 miles (again following the mile-by-mile strategy).

There is also a related problem where instead of the apples the car is transporting fuel and it consumes 1 gallon per mile traveled both ways. The goal is to find out the maximum gallons of fuel that can be transported to 1000 miles.

You can work out the DP for this :-)

Max and Min

Here are some useful equations and properties related to the max and min functions.

max is associative:

max(a, max(b, c)) = max(a, b, c)

max(x,y) is a non-decreasing function of (x,y). i.e., if x1 >= x2 and y1 >= y2, max(x1,y1) >= max(x2,y2)

max(a,b)+c = max(a+c, b+c)
max(a,b)-c = max(a-c, b-c)

max(a,b)+max(c,d)=max(a+c,a+d,b+c,b+d)

max(a,b)>= a
max(a,b)>= b
(c <= a or c <= b) => c <= max(a,b)

Expressing <= using <

Can you express a <= b using only strict less than operator?

Yes. We have a <=b <=> for all e > 0, a < b + e

Proof => Obvious!

<= Assume not. Then a > b.
Take e = a - b >0
Then by hypothesis, we have

a < b + e = b + a - b = a

Contradiction!

QED.

Great Expectations!

Came across this cool question the other day.

If X and Y are Uniform(0,1) random variables, what is E[X/(X+Y)]?

Direct calculation of the expectation as a double integral turns out to be a bit nasty.

But there is a trick.

X/(X+Y) + Y/(X+Y) = 1

=> E[X/(X+Y)] + E[Y/(X+Y)] = 1

Since X~Y, both the expectations above are equal since they are symmetrical in X and Y.

Thus each equals 1/2.

And we are done!

Corollaries:

Now it is easy to calculate the following (X, Y, Z ~ U(0,1) )


E[X/(X+Y+Z)] = 1/3
E[XY / (XY + YZ + ZX)] = 1/3

and so on!

Question:
Would the results be the same if X, Y, Z were iid but from another distribution?