Check Primitive Condition of Product of Matrices

Clash Royale CLAN TAG#URR8PPP

up vote
1
down vote

favorite

1

Consider $n-1$ Companion matrices $C^(i)$ over $mathbbR$, for $1leq i leq n-1$, which are defined by the following form:
$$
C^(i)=left(
beginarraycccccc
0 &1 &0 &cdots &cdots &0 \
0 &0 &1 &ddots &ddots &vdots \
vdots &ddots &ddots &ddots &ddots &vdots \
vdots &ddots &ddots &ddots &ddots &0 \
0 &cdots &cdots &0&0 &1 \
u_1^(i) &u_2^(i) &u_3^(i) &cdots &u_n-1^(i) &u_n^(i)
endarray
right)_ntimes n
$$
where $u_k^(i)$ for $1leq i leq n-1$ and $1leq k leq n$, are positive integer numbers.

Now consider the matrix $B=prod_i=1^n-1, C^(i)$, the product of matrices $C^(i)$.

My question: Let $B=(b_i,j)$. Then how to prove that $b_1,j=0$ for $1leq j leq n-1$.

for example for $n=3$ we have
$$
B = beginpmatrix 0 & 0 & b_1,3\ b_2,1 & b_2,2 & b_2,3\ b_3,1 & b_3,2& b_3,3 endpmatrix.
$$

My try: Consider digraphs of $C^(i)$ matrices . The elements $u_k^(i)$'s are called weight in these digraphs. Therefore, we can assume that they have the same value which means $u_k^(1)=u_k^(2)=cdots=u_k^(n-1)$ for $1leq k leq n$.

Hence it is enough to prove if $E=(C^(1))^n-1=(e_i,j)$ then why $e_1,j=0$ for $1leq j leq n-1$.
Consider digraph of $C^(i)$ then we can see that there is no walk of length $n-1$ from the vertex $v_1$ to $v_j$ for $1leq j leq n-1$ which means
$e_1,j=0$ for $1leq j leq n-1$.

Is this proof correct? If there is other proof, I appreciate you to post it.

Thanks for any suggestions.

linear-algebra matrices graph-theory

share|cite|improve this question

edited Jul 27 at 17:09

asked Jul 27 at 15:01

Amin235

1,179621

add a comment | 

up vote
1
down vote

favorite

1

Consider $n-1$ Companion matrices $C^(i)$ over $mathbbR$, for $1leq i leq n-1$, which are defined by the following form:
$$
C^(i)=left(
beginarraycccccc
0 &1 &0 &cdots &cdots &0 \
0 &0 &1 &ddots &ddots &vdots \
vdots &ddots &ddots &ddots &ddots &vdots \
vdots &ddots &ddots &ddots &ddots &0 \
0 &cdots &cdots &0&0 &1 \
u_1^(i) &u_2^(i) &u_3^(i) &cdots &u_n-1^(i) &u_n^(i)
endarray
right)_ntimes n
$$
where $u_k^(i)$ for $1leq i leq n-1$ and $1leq k leq n$, are positive integer numbers.

Now consider the matrix $B=prod_i=1^n-1, C^(i)$, the product of matrices $C^(i)$.

My question: Let $B=(b_i,j)$. Then how to prove that $b_1,j=0$ for $1leq j leq n-1$.

for example for $n=3$ we have
$$
B = beginpmatrix 0 & 0 & b_1,3\ b_2,1 & b_2,2 & b_2,3\ b_3,1 & b_3,2& b_3,3 endpmatrix.
$$

My try: Consider digraphs of $C^(i)$ matrices . The elements $u_k^(i)$'s are called weight in these digraphs. Therefore, we can assume that they have the same value which means $u_k^(1)=u_k^(2)=cdots=u_k^(n-1)$ for $1leq k leq n$.

Hence it is enough to prove if $E=(C^(1))^n-1=(e_i,j)$ then why $e_1,j=0$ for $1leq j leq n-1$.
Consider digraph of $C^(i)$ then we can see that there is no walk of length $n-1$ from the vertex $v_1$ to $v_j$ for $1leq j leq n-1$ which means
$e_1,j=0$ for $1leq j leq n-1$.

Is this proof correct? If there is other proof, I appreciate you to post it.

Thanks for any suggestions.

linear-algebra matrices graph-theory

share|cite|improve this question

edited Jul 27 at 17:09

asked Jul 27 at 15:01

Amin235

1,179621

add a comment | 

up vote
1
down vote

favorite

1

up vote
1
down vote

favorite

1

1

Consider $n-1$ Companion matrices $C^(i)$ over $mathbbR$, for $1leq i leq n-1$, which are defined by the following form:
$$
C^(i)=left(
beginarraycccccc
0 &1 &0 &cdots &cdots &0 \
0 &0 &1 &ddots &ddots &vdots \
vdots &ddots &ddots &ddots &ddots &vdots \
vdots &ddots &ddots &ddots &ddots &0 \
0 &cdots &cdots &0&0 &1 \
u_1^(i) &u_2^(i) &u_3^(i) &cdots &u_n-1^(i) &u_n^(i)
endarray
right)_ntimes n
$$
where $u_k^(i)$ for $1leq i leq n-1$ and $1leq k leq n$, are positive integer numbers.

Now consider the matrix $B=prod_i=1^n-1, C^(i)$, the product of matrices $C^(i)$.

My question: Let $B=(b_i,j)$. Then how to prove that $b_1,j=0$ for $1leq j leq n-1$.

for example for $n=3$ we have
$$
B = beginpmatrix 0 & 0 & b_1,3\ b_2,1 & b_2,2 & b_2,3\ b_3,1 & b_3,2& b_3,3 endpmatrix.
$$

My try: Consider digraphs of $C^(i)$ matrices . The elements $u_k^(i)$'s are called weight in these digraphs. Therefore, we can assume that they have the same value which means $u_k^(1)=u_k^(2)=cdots=u_k^(n-1)$ for $1leq k leq n$.

Hence it is enough to prove if $E=(C^(1))^n-1=(e_i,j)$ then why $e_1,j=0$ for $1leq j leq n-1$.
Consider digraph of $C^(i)$ then we can see that there is no walk of length $n-1$ from the vertex $v_1$ to $v_j$ for $1leq j leq n-1$ which means
$e_1,j=0$ for $1leq j leq n-1$.

Is this proof correct? If there is other proof, I appreciate you to post it.

Thanks for any suggestions.

linear-algebra matrices graph-theory

share|cite|improve this question

edited Jul 27 at 17:09

asked Jul 27 at 15:01

Amin235

1,179621

Consider $n-1$ Companion matrices $C^(i)$ over $mathbbR$, for $1leq i leq n-1$, which are defined by the following form:
$$
C^(i)=left(
beginarraycccccc
0 &1 &0 &cdots &cdots &0 \
0 &0 &1 &ddots &ddots &vdots \
vdots &ddots &ddots &ddots &ddots &vdots \
vdots &ddots &ddots &ddots &ddots &0 \
0 &cdots &cdots &0&0 &1 \
u_1^(i) &u_2^(i) &u_3^(i) &cdots &u_n-1^(i) &u_n^(i)
endarray
right)_ntimes n
$$
where $u_k^(i)$ for $1leq i leq n-1$ and $1leq k leq n$, are positive integer numbers.

Now consider the matrix $B=prod_i=1^n-1, C^(i)$, the product of matrices $C^(i)$.

My question: Let $B=(b_i,j)$. Then how to prove that $b_1,j=0$ for $1leq j leq n-1$.

for example for $n=3$ we have
$$
B = beginpmatrix 0 & 0 & b_1,3\ b_2,1 & b_2,2 & b_2,3\ b_3,1 & b_3,2& b_3,3 endpmatrix.
$$

My try: Consider digraphs of $C^(i)$ matrices . The elements $u_k^(i)$'s are called weight in these digraphs. Therefore, we can assume that they have the same value which means $u_k^(1)=u_k^(2)=cdots=u_k^(n-1)$ for $1leq k leq n$.

Hence it is enough to prove if $E=(C^(1))^n-1=(e_i,j)$ then why $e_1,j=0$ for $1leq j leq n-1$.
Consider digraph of $C^(i)$ then we can see that there is no walk of length $n-1$ from the vertex $v_1$ to $v_j$ for $1leq j leq n-1$ which means
$e_1,j=0$ for $1leq j leq n-1$.

Is this proof correct? If there is other proof, I appreciate you to post it.

Thanks for any suggestions.

linear-algebra matrices graph-theory

share|cite|improve this question

edited Jul 27 at 17:09

asked Jul 27 at 15:01

Amin235

1,179621

share|cite|improve this question

share|cite|improve this question

edited Jul 27 at 17:09

edited Jul 27 at 17:09

edited Jul 27 at 17:09

asked Jul 27 at 15:01

Amin235

1,179621

asked Jul 27 at 15:01

Amin235

1,179621

asked Jul 27 at 15:01

Amin235

1,179621

1,179621

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

up vote
1
down vote



accepted

The proof is sorta correct, but you should justify better why you can suppose all the weights as the same.

An other proof goes through noticing that
$$
e_i^T C^(k) = e_i+1^T$$
for every $k$ and every $i<n$, since $e_i^T C^(k) $ is the $i$-th row of $C^(k)$. Now you have
$$
b_1j = e_1^T B e_j = e_1^T C^(1) C^(2) dots C^(n-1) e_j =
e_2^T C^(2) C^(3) dots C^(n-1) e_j =$$$$
e_3^T C^(3) C^(4) dots C^(n-1) e_j =
dots = e_n-1^T C^(n-1) e_j
$$
and the element $(n-1,j)$ of $C^(n-1)$ is zero whenever $1le j<n$.

share|cite|improve this answer

edited Jul 27 at 17:24

answered Jul 27 at 16:29

Exodd

5,3901222

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Sorry, I inverted the indexes
  – Exodd
  Jul 27 at 17:14
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is my proof correct?
  – Amin235
  Jul 27 at 17:21
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Amin235 Yes, I've edited
  – Exodd
  Jul 27 at 17:24
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Your reasoning is correct, but you should take $u = max_i,j u_j^(i)$ and consider the matrix $C$ with $u$ instead of $u_j^(i)$. It is easy to see that $Ble C^n-1$ entry by entry, so you can repeat your reasoning for $C^n-1$.
  – Exodd
  Jul 27 at 17:45
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Amin235 The statement is still true, and my proof holds, but the proof in Graph Theory needs a bit more justifications
  – Exodd
  Jul 27 at 19:39
  

  
  
  
  

 | 
show 3 more comments

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2864467%2fcheck-primitive-condition-of-product-of-matrices%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
1
down vote



accepted

The proof is sorta correct, but you should justify better why you can suppose all the weights as the same.

An other proof goes through noticing that
$$
e_i^T C^(k) = e_i+1^T$$
for every $k$ and every $i<n$, since $e_i^T C^(k) $ is the $i$-th row of $C^(k)$. Now you have
$$
b_1j = e_1^T B e_j = e_1^T C^(1) C^(2) dots C^(n-1) e_j =
e_2^T C^(2) C^(3) dots C^(n-1) e_j =$$$$
e_3^T C^(3) C^(4) dots C^(n-1) e_j =
dots = e_n-1^T C^(n-1) e_j
$$
and the element $(n-1,j)$ of $C^(n-1)$ is zero whenever $1le j<n$.

share|cite|improve this answer

edited Jul 27 at 17:24

answered Jul 27 at 16:29

Exodd

5,3901222

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Sorry, I inverted the indexes
  – Exodd
  Jul 27 at 17:14
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is my proof correct?
  – Amin235
  Jul 27 at 17:21
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Amin235 Yes, I've edited
  – Exodd
  Jul 27 at 17:24
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Your reasoning is correct, but you should take $u = max_i,j u_j^(i)$ and consider the matrix $C$ with $u$ instead of $u_j^(i)$. It is easy to see that $Ble C^n-1$ entry by entry, so you can repeat your reasoning for $C^n-1$.
  – Exodd
  Jul 27 at 17:45
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Amin235 The statement is still true, and my proof holds, but the proof in Graph Theory needs a bit more justifications
  – Exodd
  Jul 27 at 19:39
  

  
  
  
  

 | 
show 3 more comments

up vote
1
down vote



accepted

The proof is sorta correct, but you should justify better why you can suppose all the weights as the same.

An other proof goes through noticing that
$$
e_i^T C^(k) = e_i+1^T$$
for every $k$ and every $i<n$, since $e_i^T C^(k) $ is the $i$-th row of $C^(k)$. Now you have
$$
b_1j = e_1^T B e_j = e_1^T C^(1) C^(2) dots C^(n-1) e_j =
e_2^T C^(2) C^(3) dots C^(n-1) e_j =$$$$
e_3^T C^(3) C^(4) dots C^(n-1) e_j =
dots = e_n-1^T C^(n-1) e_j
$$
and the element $(n-1,j)$ of $C^(n-1)$ is zero whenever $1le j<n$.

share|cite|improve this answer

edited Jul 27 at 17:24

answered Jul 27 at 16:29

Exodd

5,3901222

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Sorry, I inverted the indexes
  – Exodd
  Jul 27 at 17:14
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is my proof correct?
  – Amin235
  Jul 27 at 17:21
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Amin235 Yes, I've edited
  – Exodd
  Jul 27 at 17:24
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Your reasoning is correct, but you should take $u = max_i,j u_j^(i)$ and consider the matrix $C$ with $u$ instead of $u_j^(i)$. It is easy to see that $Ble C^n-1$ entry by entry, so you can repeat your reasoning for $C^n-1$.
  – Exodd
  Jul 27 at 17:45
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Amin235 The statement is still true, and my proof holds, but the proof in Graph Theory needs a bit more justifications
  – Exodd
  Jul 27 at 19:39
  

  
  
  
  

 | 
show 3 more comments

up vote
1
down vote



accepted

up vote
1
down vote



accepted

The proof is sorta correct, but you should justify better why you can suppose all the weights as the same.

An other proof goes through noticing that
$$
e_i^T C^(k) = e_i+1^T$$
for every $k$ and every $i<n$, since $e_i^T C^(k) $ is the $i$-th row of $C^(k)$. Now you have
$$
b_1j = e_1^T B e_j = e_1^T C^(1) C^(2) dots C^(n-1) e_j =
e_2^T C^(2) C^(3) dots C^(n-1) e_j =$$$$
e_3^T C^(3) C^(4) dots C^(n-1) e_j =
dots = e_n-1^T C^(n-1) e_j
$$
and the element $(n-1,j)$ of $C^(n-1)$ is zero whenever $1le j<n$.

share|cite|improve this answer

edited Jul 27 at 17:24

answered Jul 27 at 16:29

Exodd

5,3901222

The proof is sorta correct, but you should justify better why you can suppose all the weights as the same.

An other proof goes through noticing that
$$
e_i^T C^(k) = e_i+1^T$$
for every $k$ and every $i<n$, since $e_i^T C^(k) $ is the $i$-th row of $C^(k)$. Now you have
$$
b_1j = e_1^T B e_j = e_1^T C^(1) C^(2) dots C^(n-1) e_j =
e_2^T C^(2) C^(3) dots C^(n-1) e_j =$$$$
e_3^T C^(3) C^(4) dots C^(n-1) e_j =
dots = e_n-1^T C^(n-1) e_j
$$
and the element $(n-1,j)$ of $C^(n-1)$ is zero whenever $1le j<n$.

share|cite|improve this answer

edited Jul 27 at 17:24

answered Jul 27 at 16:29

Exodd

5,3901222

share|cite|improve this answer

share|cite|improve this answer

edited Jul 27 at 17:24

edited Jul 27 at 17:24

edited Jul 27 at 17:24

answered Jul 27 at 16:29

Exodd

5,3901222

answered Jul 27 at 16:29

Exodd

5,3901222

answered Jul 27 at 16:29

Exodd

5,3901222

5,3901222

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Sorry, I inverted the indexes
  – Exodd
  Jul 27 at 17:14
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is my proof correct?
  – Amin235
  Jul 27 at 17:21
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Amin235 Yes, I've edited
  – Exodd
  Jul 27 at 17:24
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Your reasoning is correct, but you should take $u = max_i,j u_j^(i)$ and consider the matrix $C$ with $u$ instead of $u_j^(i)$. It is easy to see that $Ble C^n-1$ entry by entry, so you can repeat your reasoning for $C^n-1$.
  – Exodd
  Jul 27 at 17:45
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Amin235 The statement is still true, and my proof holds, but the proof in Graph Theory needs a bit more justifications
  – Exodd
  Jul 27 at 19:39
  

  
  
  
  

 | 
show 3 more comments

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Sorry, I inverted the indexes
  – Exodd
  Jul 27 at 17:14
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is my proof correct?
  – Amin235
  Jul 27 at 17:21
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Amin235 Yes, I've edited
  – Exodd
  Jul 27 at 17:24
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Your reasoning is correct, but you should take $u = max_i,j u_j^(i)$ and consider the matrix $C$ with $u$ instead of $u_j^(i)$. It is easy to see that $Ble C^n-1$ entry by entry, so you can repeat your reasoning for $C^n-1$.
  – Exodd
  Jul 27 at 17:45
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Amin235 The statement is still true, and my proof holds, but the proof in Graph Theory needs a bit more justifications
  – Exodd
  Jul 27 at 19:39
  

  
  
  
  

Sorry, I inverted the indexes
– Exodd
Jul 27 at 17:14

Sorry, I inverted the indexes
– Exodd
Jul 27 at 17:14

Is my proof correct?
– Amin235
Jul 27 at 17:21

Is my proof correct?
– Amin235
Jul 27 at 17:21

@Amin235 Yes, I've edited
– Exodd
Jul 27 at 17:24

@Amin235 Yes, I've edited
– Exodd
Jul 27 at 17:24

1

1

Your reasoning is correct, but you should take $u = max_i,j u_j^(i)$ and consider the matrix $C$ with $u$ instead of $u_j^(i)$. It is easy to see that $Ble C^n-1$ entry by entry, so you can repeat your reasoning for $C^n-1$.
– Exodd
Jul 27 at 17:45

Your reasoning is correct, but you should take $u = max_i,j u_j^(i)$ and consider the matrix $C$ with $u$ instead of $u_j^(i)$. It is easy to see that $Ble C^n-1$ entry by entry, so you can repeat your reasoning for $C^n-1$.
– Exodd
Jul 27 at 17:45

1

1

@Amin235 The statement is still true, and my proof holds, but the proof in Graph Theory needs a bit more justifications
– Exodd
Jul 27 at 19:39

@Amin235 The statement is still true, and my proof holds, but the proof in Graph Theory needs a bit more justifications
– Exodd
Jul 27 at 19:39

 | 
show 3 more comments

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2864467%2fcheck-primitive-condition-of-product-of-matrices%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email