Fdtxjr

How to color a curve

Drawing ramified coverings with tikz

anything or something to eat

Reply 'no position' while the job posting is still there

Translation of Scottish 16th century church stained glass

Journal losing indexing services

Can a significant change in incentives void an employment contract?

How must one send away the mother bird?

Are lightweight LN wallets vulnerable to transaction withholding?

Why has "pence" been used in this sentence, not "pences"?

Flux received by a negative charge

Does the Mind Blank spell prevent the target from being frightened?

Do the concepts of IP address and network interface not belong to the same layer?

Should I install hardwood flooring or cabinets first?

Hot bath for aluminium engine block and heads

Varistor? Purpose and principle

Two-sided logarithm inequality

Longest common substring in linear time

What is this type of notehead called?

Should I stop contributing to retirement accounts?

Find last 3 digits of this monster number

What linear sensor for a keyboard?

Drawing a topological "handle" with Tikz

Freedom of speech and where it applies

Prove a real block tridiagonal matrix is invertible

Eigendecomposition of a large symmetric block tridiagonal matrix.Properties of Non-Diagonally Dominant MatrixFinding eigenvalues of a block matrixWhen is Block-Partitioned Matrix Invertible?Determinant of block tridiagonal Toeplitz matricesMaximum norm bound on a block diagonal matrix inverseSufficient conditions for positive semidefiniteness of block matrixInverse of a rectangular block diagonal matrixIf a matrix is symmetric, tridiagonal, and diagonally dominant, is it positive definite?Inverse of strictly diagonally dominant matrix

3

2

$begingroup$

Suppose matrix $A$ is a real block tridiagonal matrix where the blocks are all size $q times q$ and the diagonal blocks $D_i$ are all invertible ($1 leq i leq n$). Furthermore, $A^t$ is block diagonally dominant.

(a) Prove $A$ is invertible.

(b) Prove $A$ has an $LU$ decomposition.

Not sure where to start. Thought I can decompose $A=D-L-U$ but got nothing. Tried to find the inverse of $A$ directly but it got really messy and we only know the diagonal entries $D_i$ are invertible.

linear-algebra matrices block-matrices

share|cite|improve this question

edited Mar 16 at 8:05

Rodrigo de Azevedo

13.2k41960

asked Dec 31 '16 at 17:32

Er WenEr Wen

434

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Can you confirm that $A^T$ is strictly block diagonally dominant? I believe this condition is necessary for invertibility.
  $endgroup$
  – K. Miller
  Dec 31 '16 at 17:53
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @K.Miller Thanks for reply. Yes, it's strict. I knew if the norm of a matrix $M$ $<1$, then $I-M$ is invertible, but I don't know how to apply to here.
  $endgroup$
  – Er Wen
  Dec 31 '16 at 18:01
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @K.Miller Thanks for reply. Yes, it's strict. I knew if the norm of a matrix $M$ is $<1$, then $I-M$ is invertible, but I don't know how to apply to here.
  $endgroup$
  – Er Wen
  Dec 31 '16 at 18:03
  

  
  
  
  

add a comment | 

3

2

$begingroup$

Suppose matrix $A$ is a real block tridiagonal matrix where the blocks are all size $q times q$ and the diagonal blocks $D_i$ are all invertible ($1 leq i leq n$). Furthermore, $A^t$ is block diagonally dominant.

(a) Prove $A$ is invertible.

(b) Prove $A$ has an $LU$ decomposition.

Not sure where to start. Thought I can decompose $A=D-L-U$ but got nothing. Tried to find the inverse of $A$ directly but it got really messy and we only know the diagonal entries $D_i$ are invertible.

linear-algebra matrices block-matrices

share|cite|improve this question

edited Mar 16 at 8:05

Rodrigo de Azevedo

13.2k41960

asked Dec 31 '16 at 17:32

Er WenEr Wen

434

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Can you confirm that $A^T$ is strictly block diagonally dominant? I believe this condition is necessary for invertibility.
  $endgroup$
  – K. Miller
  Dec 31 '16 at 17:53
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @K.Miller Thanks for reply. Yes, it's strict. I knew if the norm of a matrix $M$ $<1$, then $I-M$ is invertible, but I don't know how to apply to here.
  $endgroup$
  – Er Wen
  Dec 31 '16 at 18:01
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @K.Miller Thanks for reply. Yes, it's strict. I knew if the norm of a matrix $M$ is $<1$, then $I-M$ is invertible, but I don't know how to apply to here.
  $endgroup$
  – Er Wen
  Dec 31 '16 at 18:03
  

  
  
  
  

add a comment | 

$begingroup$

Suppose matrix $A$ is a real block tridiagonal matrix where the blocks are all size $q times q$ and the diagonal blocks $D_i$ are all invertible ($1 leq i leq n$). Furthermore, $A^t$ is block diagonally dominant.

(a) Prove $A$ is invertible.

(b) Prove $A$ has an $LU$ decomposition.

Not sure where to start. Thought I can decompose $A=D-L-U$ but got nothing. Tried to find the inverse of $A$ directly but it got really messy and we only know the diagonal entries $D_i$ are invertible.

linear-algebra matrices block-matrices

share|cite|improve this question

edited Mar 16 at 8:05

Rodrigo de Azevedo

13.2k41960

asked Dec 31 '16 at 17:32

Er WenEr Wen

434

$endgroup$

share|cite|improve this question

edited Mar 16 at 8:05

Rodrigo de Azevedo

13.2k41960

asked Dec 31 '16 at 17:32

Er WenEr Wen

434

share|cite|improve this question

edited Mar 16 at 8:05

Rodrigo de Azevedo

13.2k41960

asked Dec 31 '16 at 17:32

Er WenEr Wen

434

edited Mar 16 at 8:05

Rodrigo de Azevedo

13.2k41960

edited Mar 16 at 8:05

Rodrigo de Azevedo

13.2k41960

asked Dec 31 '16 at 17:32

Er WenEr Wen

434

asked Dec 31 '16 at 17:32

Er WenEr Wen

434

1 Answer
1

active

oldest

votes

2

$begingroup$

I will help you with part (a). For part (b) see the technical report "Block LU Factorization" by Demmel, Higham, and Schreiber.

Let $B = A^T$ and let $B_i,j$ denote the $(i,j)$ block of $B$. Then $B$ is strictly block diagonally dominant if

$$
(|B_i,i^-1|)^-1 > sum_jneq i |B_i,j|~~textfor all~~i = 1,ldots,n,
$$

where $|cdot|$ is some induced matrix norm. Suppose there exists a nonzero vector $xinmathbbR^nq$ partitioned into blocks if size $q$ according to $x = (x_1,ldots,x_n)^T$ such that $Bx = 0$. Without restricting generality suppose that $|x| = 1$. Clearly, there exists an index $i$ such that $0 < |x_i| = max_k=1,ldots,n|x_k|$. Thus

$$
B_i,ix_i = -sum_jneq i B_i,jx_j implies |x_i| = big|B_i,i^-1sum_jneq i B_i,jx_jbig| leq |B_i,i^-1|cdotbig|sum_jneq iB_i,jx_jbig|
$$

By the triangle inequality it follows that

$$
|x_i|(|B_i,i^-1|)^-1 leq sum_jneq i |B_i,j|cdot|x_j| implies (|B_i,i^-1|)^-1 leq sum_jneq i |B_i,j|cdotfrac
$$

Since $|x_i|$ is the maximum such norm we arrive at the contradiction that

$$
(|B_i,i^-1|)^-1 leq sum_jneq i |B_i,j|
$$

Therefore no such vector exists and consequently $B$ is invertible. Since $B = A^T$, $A$ is invertible.

share|cite|improve this answer

answered Dec 31 '16 at 19:12

K. MillerK. Miller

3,663612

$endgroup$

add a comment | 

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',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
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

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2078666%2fprove-a-real-block-tridiagonal-matrix-is-invertible%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

I will help you with part (a). For part (b) see the technical report "Block LU Factorization" by Demmel, Higham, and Schreiber.

Let $B = A^T$ and let $B_i,j$ denote the $(i,j)$ block of $B$. Then $B$ is strictly block diagonally dominant if

$$
(|B_i,i^-1|)^-1 > sum_jneq i |B_i,j|~~textfor all~~i = 1,ldots,n,
$$

where $|cdot|$ is some induced matrix norm. Suppose there exists a nonzero vector $xinmathbbR^nq$ partitioned into blocks if size $q$ according to $x = (x_1,ldots,x_n)^T$ such that $Bx = 0$. Without restricting generality suppose that $|x| = 1$. Clearly, there exists an index $i$ such that $0 < |x_i| = max_k=1,ldots,n|x_k|$. Thus

$$
B_i,ix_i = -sum_jneq i B_i,jx_j implies |x_i| = big|B_i,i^-1sum_jneq i B_i,jx_jbig| leq |B_i,i^-1|cdotbig|sum_jneq iB_i,jx_jbig|
$$

By the triangle inequality it follows that

$$
|x_i|(|B_i,i^-1|)^-1 leq sum_jneq i |B_i,j|cdot|x_j| implies (|B_i,i^-1|)^-1 leq sum_jneq i |B_i,j|cdotfrac
$$

Since $|x_i|$ is the maximum such norm we arrive at the contradiction that

$$
(|B_i,i^-1|)^-1 leq sum_jneq i |B_i,j|
$$

Therefore no such vector exists and consequently $B$ is invertible. Since $B = A^T$, $A$ is invertible.

share|cite|improve this answer

answered Dec 31 '16 at 19:12

K. MillerK. Miller

3,663612

$endgroup$

add a comment | 

2

$begingroup$

I will help you with part (a). For part (b) see the technical report "Block LU Factorization" by Demmel, Higham, and Schreiber.

Let $B = A^T$ and let $B_i,j$ denote the $(i,j)$ block of $B$. Then $B$ is strictly block diagonally dominant if

$$
(|B_i,i^-1|)^-1 > sum_jneq i |B_i,j|~~textfor all~~i = 1,ldots,n,
$$

where $|cdot|$ is some induced matrix norm. Suppose there exists a nonzero vector $xinmathbbR^nq$ partitioned into blocks if size $q$ according to $x = (x_1,ldots,x_n)^T$ such that $Bx = 0$. Without restricting generality suppose that $|x| = 1$. Clearly, there exists an index $i$ such that $0 < |x_i| = max_k=1,ldots,n|x_k|$. Thus

$$
B_i,ix_i = -sum_jneq i B_i,jx_j implies |x_i| = big|B_i,i^-1sum_jneq i B_i,jx_jbig| leq |B_i,i^-1|cdotbig|sum_jneq iB_i,jx_jbig|
$$

By the triangle inequality it follows that

$$
|x_i|(|B_i,i^-1|)^-1 leq sum_jneq i |B_i,j|cdot|x_j| implies (|B_i,i^-1|)^-1 leq sum_jneq i |B_i,j|cdotfrac
$$

Since $|x_i|$ is the maximum such norm we arrive at the contradiction that

$$
(|B_i,i^-1|)^-1 leq sum_jneq i |B_i,j|
$$

Therefore no such vector exists and consequently $B$ is invertible. Since $B = A^T$, $A$ is invertible.

share|cite|improve this answer

answered Dec 31 '16 at 19:12

K. MillerK. Miller

3,663612

$endgroup$

add a comment | 

$begingroup$

I will help you with part (a). For part (b) see the technical report "Block LU Factorization" by Demmel, Higham, and Schreiber.

Let $B = A^T$ and let $B_i,j$ denote the $(i,j)$ block of $B$. Then $B$ is strictly block diagonally dominant if

$$
(|B_i,i^-1|)^-1 > sum_jneq i |B_i,j|~~textfor all~~i = 1,ldots,n,
$$

where $|cdot|$ is some induced matrix norm. Suppose there exists a nonzero vector $xinmathbbR^nq$ partitioned into blocks if size $q$ according to $x = (x_1,ldots,x_n)^T$ such that $Bx = 0$. Without restricting generality suppose that $|x| = 1$. Clearly, there exists an index $i$ such that $0 < |x_i| = max_k=1,ldots,n|x_k|$. Thus

$$
B_i,ix_i = -sum_jneq i B_i,jx_j implies |x_i| = big|B_i,i^-1sum_jneq i B_i,jx_jbig| leq |B_i,i^-1|cdotbig|sum_jneq iB_i,jx_jbig|
$$

By the triangle inequality it follows that

$$
|x_i|(|B_i,i^-1|)^-1 leq sum_jneq i |B_i,j|cdot|x_j| implies (|B_i,i^-1|)^-1 leq sum_jneq i |B_i,j|cdotfrac
$$

Since $|x_i|$ is the maximum such norm we arrive at the contradiction that

$$
(|B_i,i^-1|)^-1 leq sum_jneq i |B_i,j|
$$

Therefore no such vector exists and consequently $B$ is invertible. Since $B = A^T$, $A$ is invertible.

share|cite|improve this answer

answered Dec 31 '16 at 19:12

K. MillerK. Miller

3,663612

$endgroup$

share|cite|improve this answer

answered Dec 31 '16 at 19:12

K. MillerK. Miller

3,663612

answered Dec 31 '16 at 19:12

K. MillerK. Miller

3,663612

answered Dec 31 '16 at 19:12

K. MillerK. Miller

3,663612