Dtjytyk

What does "Puller Prush Person" mean?

LaTeX: Why are digits allowed in environments, but forbidden in commands?

How can bays and straits be determined in a procedurally generated map?

Important Resources for Dark Age Civilizations?

Do I have a twin with permutated remainders?

How much of data wrangling is a data scientist's job?

Unable to deploy metadata from Partner Developer scratch org because of extra fields

dbcc cleantable batch size explanation

Why do I get two different answers for this counting problem?

How to determine what difficulty is right for the game?

Why doesn't H₄O²⁺ exist?

Are the number of citations and number of published articles the most important criteria for a tenure promotion?

Accidentally leaked the solution to an assignment, what to do now? (I'm the prof)

Rock identification in KY

Is it possible to run Internet Explorer on OS X El Capitan?

A case of the sniffles

Why doesn't Newton's third law mean a person bounces back to where they started when they hit the ground?

I'm flying to France today and my passport expires in less than 2 months

Watching something be written to a file live with tail

Is it legal for company to use my work email to pretend I still work there?

A newer friend of my brother's gave him a load of baseball cards that are supposedly extremely valuable. Is this a scam?

Codimension of non-flat locus

Can I ask the recruiters in my resume to put the reason why I am rejected?

Can a Cauchy sequence converge for one metric while not converging for another?

Invertibility of $I + AB(x)$

can one identify $U'A$ from the following decomposition?Gaussian Elimination and Matrix questionBest way to solve specific block-tridiagonal linear system (10000x10000 and larger)Analytical solution to nonlinear least-squares problemMatrix Solvers for High Condition NumbersPivots and singular cases in Gaussian EliminationFinding real eigenvectors of non symmetric real matrixIs there a fundamental problem with extending matrix concepts to tensors?Let $Xinmathcal{M}_{ntimes p}(mathbb{R})$ with rank(X)=k and let $epsilon sim N(0,I_p)$ be a vector with i.i.d. Gaussian components.Finding the square of an eigenvalue in a Generalized eigenvalue problem

0

$begingroup$

I am dealing with a matrix $$I + AB(x)$$ where $A, B(x)$ are square $ntimes n$ real matrices and $x$ is a real variable. I want to find the values of $x$ for which this matrix is singular (and then an eigenvector). $A$ is invertible and $B(x)$ is invertible for the values of $x$ I am looking for. I looked into:

• Determinant: plainly awful


• Gaussian elimination: a bit better but leads to $n$ lengthy equations


• Neumann series: useless because it is not a necessary and sufficient condition


• Generalized eigenvalue: not very familiar with this theory but looks more suitable for numerical approximation

Any other ideas would be very appreciated! (For clarity I am hoping to find a somewhat palatable equation for x...)
Thanks
p

linear-algebra matrix-equations

share|cite|improve this question

edited Mar 19 at 15:34

phaedo

asked Mar 19 at 14:51

phaedophaedo

12610

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Invertibility of $I+AB(x)$ is equivalent to that of $A^{-1}+B(x)$ if $A$ is invertible. It might be of use..
  $endgroup$
  – Berci
  Mar 19 at 14:57
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Is the dependence of B on x linear, and does the variable x appear in each element of B? If so, then the determinant of @Berci's matrix will be an nth order polynomial. To find where it is singular you just need to find the zeros of that determinant, and you could use Newton's method or similar numerical scheme to find them.
  $endgroup$
  – Andrew
  Mar 19 at 14:57
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  B(x) is not linear but it is a "nice" analytic function
  $endgroup$
  – phaedo
  Mar 19 at 15:08
  

  
  
  
  

add a comment | 

0

$begingroup$

I am dealing with a matrix $$I + AB(x)$$ where $A, B(x)$ are square $ntimes n$ real matrices and $x$ is a real variable. I want to find the values of $x$ for which this matrix is singular (and then an eigenvector). $A$ is invertible and $B(x)$ is invertible for the values of $x$ I am looking for. I looked into:

• Determinant: plainly awful


• Gaussian elimination: a bit better but leads to $n$ lengthy equations


• Neumann series: useless because it is not a necessary and sufficient condition


• Generalized eigenvalue: not very familiar with this theory but looks more suitable for numerical approximation

Any other ideas would be very appreciated! (For clarity I am hoping to find a somewhat palatable equation for x...)
Thanks
p

linear-algebra matrix-equations

share|cite|improve this question

edited Mar 19 at 15:34

phaedo

asked Mar 19 at 14:51

phaedophaedo

12610

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Invertibility of $I+AB(x)$ is equivalent to that of $A^{-1}+B(x)$ if $A$ is invertible. It might be of use..
  $endgroup$
  – Berci
  Mar 19 at 14:57
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Is the dependence of B on x linear, and does the variable x appear in each element of B? If so, then the determinant of @Berci's matrix will be an nth order polynomial. To find where it is singular you just need to find the zeros of that determinant, and you could use Newton's method or similar numerical scheme to find them.
  $endgroup$
  – Andrew
  Mar 19 at 14:57
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  B(x) is not linear but it is a "nice" analytic function
  $endgroup$
  – phaedo
  Mar 19 at 15:08
  

  
  
  
  

add a comment | 

$begingroup$

I am dealing with a matrix $$I + AB(x)$$ where $A, B(x)$ are square $ntimes n$ real matrices and $x$ is a real variable. I want to find the values of $x$ for which this matrix is singular (and then an eigenvector). $A$ is invertible and $B(x)$ is invertible for the values of $x$ I am looking for. I looked into:

• Determinant: plainly awful


• Gaussian elimination: a bit better but leads to $n$ lengthy equations


• Neumann series: useless because it is not a necessary and sufficient condition


• Generalized eigenvalue: not very familiar with this theory but looks more suitable for numerical approximation

Any other ideas would be very appreciated! (For clarity I am hoping to find a somewhat palatable equation for x...)
Thanks
p

linear-algebra matrix-equations

share|cite|improve this question

edited Mar 19 at 15:34

phaedo

asked Mar 19 at 14:51

phaedophaedo

12610

$endgroup$

share|cite|improve this question

edited Mar 19 at 15:34

phaedo

asked Mar 19 at 14:51

phaedophaedo

12610

share|cite|improve this question

edited Mar 19 at 15:34

phaedo

asked Mar 19 at 14:51

phaedophaedo

12610

asked Mar 19 at 14:51

phaedophaedo

12610

asked Mar 19 at 14:51

phaedophaedo

12610

2 Answers
2

active

oldest

votes

1

$begingroup$

Presumably $B(x)$ is a nice analytic function of $x$, maybe polynomial.
Determinant is not necessarily so awful: its computation (for a particular matrix) takes about the same time as Gaussian elimination. You might
try Newton's method, using Jacobi's formula to compute the derivatives.

share|cite|improve this answer

answered Mar 19 at 15:03

Robert IsraelRobert Israel

330k23219473

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you for your suggestion! B(x) is not polynomial but it is indeed analytic and expandable in power series. I had a brief look into Jacobi's formula earlier and I was a bit concerned about the adjugate matrix, but perhaps it's doable. Presumably I can't use the simplified formula without adjugate involving the inverse of $I+AB(x)$...
  $endgroup$
  – phaedo
  Mar 19 at 15:16
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  If the adjugate is a problem you could use a quasi-Newton method that approximates the derivative rather than actually computing it.
  $endgroup$
  – Robert Israel
  Mar 19 at 15:40
  

  
  
  
  

add a comment | 

1

$begingroup$

We can simplify the equation a bit more using the Singular Value Decomposition of $A$ as follows:$$A=UDVimplies |I+AB(x)|{=|I+UDVB(x)|\=|U^H+DVB(x)|\=|U^HU+DVB(x)U|\=|I+DVB(x)U|\triangleq |I+DC(x)|}$$where $D$ is diagonal, $U$ and $V$ are unitary and $C(x)triangleq VB(x)U$, but this time, the singularity of $I+AB(x)$ is equivalent to the singularity of $I+DC(x)$, with $D$ being diagonal. Any constraint on $C(x)$ then, can be converted to that for $B(x)$, and as @RobertIsrael said, if $B(x)$ is a nice function, then so is $C(x)$. I think this might reduce the computation time as $D$ is diagonal. Even you can use $|D^{-1}+C(x)|$ to decide.

share|cite|improve this answer

answered Mar 19 at 16:55

Mostafa AyazMostafa Ayaz

18.2k31040

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you. Why SVD rather than eigendecomposition? To avoid complexes?
  $endgroup$
  – phaedo
  Mar 19 at 17:15
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Your welcome. Also eigendecomposition looks much helpful but is not as general as SVD which applies to all kind of matrices [ even non-square :) ]. The eigendecomposition is useful only for diagonalizable matrices.
  $endgroup$
  – Mostafa Ayaz
  Mar 19 at 17:18
  

  
  
  
  

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%2f3154164%2finvertibility-of-i-abx%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

Presumably $B(x)$ is a nice analytic function of $x$, maybe polynomial.
Determinant is not necessarily so awful: its computation (for a particular matrix) takes about the same time as Gaussian elimination. You might
try Newton's method, using Jacobi's formula to compute the derivatives.

share|cite|improve this answer

answered Mar 19 at 15:03

Robert IsraelRobert Israel

330k23219473

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you for your suggestion! B(x) is not polynomial but it is indeed analytic and expandable in power series. I had a brief look into Jacobi's formula earlier and I was a bit concerned about the adjugate matrix, but perhaps it's doable. Presumably I can't use the simplified formula without adjugate involving the inverse of $I+AB(x)$...
  $endgroup$
  – phaedo
  Mar 19 at 15:16
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  If the adjugate is a problem you could use a quasi-Newton method that approximates the derivative rather than actually computing it.
  $endgroup$
  – Robert Israel
  Mar 19 at 15:40
  

  
  
  
  

add a comment | 

1

$begingroup$

Presumably $B(x)$ is a nice analytic function of $x$, maybe polynomial.
Determinant is not necessarily so awful: its computation (for a particular matrix) takes about the same time as Gaussian elimination. You might
try Newton's method, using Jacobi's formula to compute the derivatives.

share|cite|improve this answer

answered Mar 19 at 15:03

Robert IsraelRobert Israel

330k23219473

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you for your suggestion! B(x) is not polynomial but it is indeed analytic and expandable in power series. I had a brief look into Jacobi's formula earlier and I was a bit concerned about the adjugate matrix, but perhaps it's doable. Presumably I can't use the simplified formula without adjugate involving the inverse of $I+AB(x)$...
  $endgroup$
  – phaedo
  Mar 19 at 15:16
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  If the adjugate is a problem you could use a quasi-Newton method that approximates the derivative rather than actually computing it.
  $endgroup$
  – Robert Israel
  Mar 19 at 15:40
  

  
  
  
  

add a comment | 

$begingroup$

Presumably $B(x)$ is a nice analytic function of $x$, maybe polynomial.
Determinant is not necessarily so awful: its computation (for a particular matrix) takes about the same time as Gaussian elimination. You might
try Newton's method, using Jacobi's formula to compute the derivatives.

share|cite|improve this answer

answered Mar 19 at 15:03

Robert IsraelRobert Israel

330k23219473

$endgroup$

share|cite|improve this answer

answered Mar 19 at 15:03

Robert IsraelRobert Israel

330k23219473

answered Mar 19 at 15:03

Robert IsraelRobert Israel

330k23219473

answered Mar 19 at 15:03

Robert IsraelRobert Israel

330k23219473

1

$begingroup$

We can simplify the equation a bit more using the Singular Value Decomposition of $A$ as follows:$$A=UDVimplies |I+AB(x)|{=|I+UDVB(x)|\=|U^H+DVB(x)|\=|U^HU+DVB(x)U|\=|I+DVB(x)U|\triangleq |I+DC(x)|}$$where $D$ is diagonal, $U$ and $V$ are unitary and $C(x)triangleq VB(x)U$, but this time, the singularity of $I+AB(x)$ is equivalent to the singularity of $I+DC(x)$, with $D$ being diagonal. Any constraint on $C(x)$ then, can be converted to that for $B(x)$, and as @RobertIsrael said, if $B(x)$ is a nice function, then so is $C(x)$. I think this might reduce the computation time as $D$ is diagonal. Even you can use $|D^{-1}+C(x)|$ to decide.

share|cite|improve this answer

answered Mar 19 at 16:55

Mostafa AyazMostafa Ayaz

18.2k31040

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you. Why SVD rather than eigendecomposition? To avoid complexes?
  $endgroup$
  – phaedo
  Mar 19 at 17:15
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Your welcome. Also eigendecomposition looks much helpful but is not as general as SVD which applies to all kind of matrices [ even non-square :) ]. The eigendecomposition is useful only for diagonalizable matrices.
  $endgroup$
  – Mostafa Ayaz
  Mar 19 at 17:18
  

  
  
  
  

add a comment | 

1

$begingroup$

We can simplify the equation a bit more using the Singular Value Decomposition of $A$ as follows:$$A=UDVimplies |I+AB(x)|{=|I+UDVB(x)|\=|U^H+DVB(x)|\=|U^HU+DVB(x)U|\=|I+DVB(x)U|\triangleq |I+DC(x)|}$$where $D$ is diagonal, $U$ and $V$ are unitary and $C(x)triangleq VB(x)U$, but this time, the singularity of $I+AB(x)$ is equivalent to the singularity of $I+DC(x)$, with $D$ being diagonal. Any constraint on $C(x)$ then, can be converted to that for $B(x)$, and as @RobertIsrael said, if $B(x)$ is a nice function, then so is $C(x)$. I think this might reduce the computation time as $D$ is diagonal. Even you can use $|D^{-1}+C(x)|$ to decide.

share|cite|improve this answer

answered Mar 19 at 16:55

Mostafa AyazMostafa Ayaz

18.2k31040

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you. Why SVD rather than eigendecomposition? To avoid complexes?
  $endgroup$
  – phaedo
  Mar 19 at 17:15
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Your welcome. Also eigendecomposition looks much helpful but is not as general as SVD which applies to all kind of matrices [ even non-square :) ]. The eigendecomposition is useful only for diagonalizable matrices.
  $endgroup$
  – Mostafa Ayaz
  Mar 19 at 17:18
  

  
  
  
  

add a comment | 

$begingroup$

We can simplify the equation a bit more using the Singular Value Decomposition of $A$ as follows:$$A=UDVimplies |I+AB(x)|{=|I+UDVB(x)|\=|U^H+DVB(x)|\=|U^HU+DVB(x)U|\=|I+DVB(x)U|\triangleq |I+DC(x)|}$$where $D$ is diagonal, $U$ and $V$ are unitary and $C(x)triangleq VB(x)U$, but this time, the singularity of $I+AB(x)$ is equivalent to the singularity of $I+DC(x)$, with $D$ being diagonal. Any constraint on $C(x)$ then, can be converted to that for $B(x)$, and as @RobertIsrael said, if $B(x)$ is a nice function, then so is $C(x)$. I think this might reduce the computation time as $D$ is diagonal. Even you can use $|D^{-1}+C(x)|$ to decide.

share|cite|improve this answer

answered Mar 19 at 16:55

Mostafa AyazMostafa Ayaz

18.2k31040

$endgroup$

share|cite|improve this answer

answered Mar 19 at 16:55

Mostafa AyazMostafa Ayaz

18.2k31040

answered Mar 19 at 16:55

Mostafa AyazMostafa Ayaz

18.2k31040

answered Mar 19 at 16:55

Mostafa AyazMostafa Ayaz

18.2k31040