When a unique solution is found for a matrix of unknown coefficients, A, that have infinite solutions? How to optimise trace(A) s.t. row sum 1?

Feb 2020
3
0
UK
Hello!

I am new here, and I need urgent help regarding the following question.

Let $\boldsymbol{A}_{(n\times n)}=[a_{ij}]$ be a square matrix such that the sum of each row is 1 and $a_{ij}\ge0$$(i=1,2,\dots,n~\text{and}~j=1,2,\dots,n)$ are unknown. Suppose that $\boldsymbol{b}_{1}=[b_{11}~b_{12}\dots b_{1n}]$ and $\boldsymbol{b}_{2}=[b_{21}~b_{22}\dots b_{2n}]$ are known row vectors of proportions such that $$\boldsymbol{b}_{1}\boldsymbol{A}_{(n\times n)}=\boldsymbol{b}_{2},$$ where $\boldsymbol{b}_{1}\boldsymbol{1}_{n}=1$, $\boldsymbol{b}_{2}\boldsymbol{1}_{n}=1$ and $\boldsymbol{1}^{T}_{n}=[1~1\dots1]$.

I know that there are infinite solutions for $\boldsymbol{A}$. However, my objective is two-folded:

(i) to optimize $\boldsymbol{A}$ such that trace$(\boldsymbol{A})$ is maximized (and each $a_{ij}$ may be expressed in terms of known quantities of the vectors $\boldsymbol{b}_{1}$ and $\boldsymbol{b}_{2}$ if possible) and
(ii) under which condition(s) a unique $\boldsymbol{A}$ exists?

Thank you!
 

romsek

Math Team
Sep 2015
2,964
1,674
USA
I may be missing something fundamental among all the trees but this seems, from toying with it in $\mathbb{R^3}$ a very difficult problem.

Basically you have a Markov Chain problem going on here.

The vectors $b_1, b_2$ represent different state probabilities. $A$ is a state transition matrix

You want to find the $A$ that propagates state probability vector $b_1$ to $b_2$

and among those find the one with the maximum trace.

Let's consider an $n\times n$ system. You've got $n$ constraints on the matrix coefficients. You've got 2 constraints on the state probability vectors.
So you've got $n^2 - n - 2$ degrees of freedom.

I'd think it almost certain that to maximize the trace you set $n^2-n-2$ diagonal entries as $1$ and the rest are computed from the conditions.
 
Feb 2020
3
0
UK
I may be missing something fundamental among all the trees but this seems, from toying with it in $\mathbb{R^3}$ a very difficult problem.

Basically you have a Markov Chain problem going on here.

The vectors $b_1, b_2$ represent different state probabilities. $A$ is a state transition matrix

You want to find the $A$ that propagates state probability vector $b_1$ to $b_2$

and among those find the one with the maximum trace.

Let's consider an $n\times n$ system. You've got $n$ constraints on the matrix coefficients. You've got 2 constraints on the state probability vectors.
So you've got $n^2 - n - 2$ degrees of freedom.

I'd think it almost certain that to maximize the trace you set $n^2-n-2$ diagonal entries as $1$ and the rest are computed from the conditions.
Thank you for your response.

Yes, you are right about what I am looking for. So you mean to say that for a 3x3 case, I should set $(3)^{2}-3-2=4$ diagonal entries equal to 1; the rest of non-diagonal entries of $\boldsymbol{A}_{3\times 3}$ can be obtained from the conditions. Is it?

If this is what you mean, then I am a little confused because I have three diagonal entries for a 3x3 transition matrix. Apologies for not understanding your exact point of saying about "...maximize the trace you set $n^2-n-2$ diagonal entries as $1$ ...".

Would you mind elaborating this for a 3x3 case?

Thank you
 

romsek

Math Team
Sep 2015
2,964
1,674
USA
Thank you for your response.

Yes, you are right about what I am looking for. So you mean to say that for a 3x3 case, I should set $(3)^{2}-3-2=4$ diagonal entries equal to 1; the rest of non-diagonal entries of $\boldsymbol{A}_{3\times 3}$ can be obtained from the conditions. Is it?

If this is what you mean, then I am a little confused because I have three diagonal entries for a 3x3 transition matrix. Apologies for not understanding your exact point of saying about "...maximize the trace you set $n^2-n-2$ diagonal entries as $1$ ...".

Would you mind elaborating this for a 3x3 case?

Thank you
Yeah this isn't correct. You have a total of $n^2 - n - 2$ free variables but probably only $n-1$ of them lie on the diagonal. I only looked at the 3x3 case and this was how it was.

Let me see if I can do the 4x4 case and see if there's some pattern.
 
  • Like
Reactions: zeeshas901
Feb 2020
3
0
UK
Yeah this isn't correct. You have a total of $n^2 - n - 2$ free variables but probably only $n-1$ of them lie on the diagonal. I only looked at the 3x3 case and this was how it was.

Let me see if I can do the 4x4 case and see if there's some pattern.
Thank you for replying.

Consider a 3x3 case as follows.

Let $\boldsymbol{b}_{1}=[5/10~~3/10~~2/10]$ and $\boldsymbol{b}_{2}=[7/10~~2/10~~1/10]$. Thus, one possible solution for $\boldsymbol{A}$ for which trace is (possibly) maximum is:

$\boldsymbol{A}=[\boldsymbol{a}_{1} ;\boldsymbol{a}_{2};\boldsymbol{a}_{3}]=\left[1~~0~~0;~~1/3~~2/3~~0;~~1/2~~0~~1/2\right]$ with $\text{trace}(\boldsymbol{A})=11/6,$ where semi-colon separtes the rows and $\boldsymbol{a}_{i}$ is row vector (i=1,2,3).

In the understudy example, is there any other matrix $\boldsymbol{A}$ for which has greater than 11/6? If not, then I am not sure that "...$n-1$ of them lie on the diagonal" is true. This is because if I place any $3-1=2$ diagonal entries equal to 1 for this example, then I possibly may not obtain $\boldsymbol{b}_{2}=[7/10~~2/10~~1/10]$ that changes from $\boldsymbol{b}_{1}=[5/10~~3/10~~2/10]$. Isn't it? Please correct if I am wrong.

Waiting for your reply about the 4x4 case.

Many thanks in advance.