Questions on the various algorithms used in linear algebra computations (matrix computations).

learn more… | top users | synonyms

1
vote
1answer
37 views

A problem about lub and glb of matrix

For any matrix $A\in \mathbb{C}^{n\times n}$, define $$lub_K(A):= \inf\{\alpha\geq 0: AK\subset \alpha K\},$$ and $$glb_K(A):= \sup\{\alpha\geq 0: \alpha K\subset AK\},$$ where $K$ is a equilibrated ...
0
votes
1answer
142 views

subtraction between sum of all elements of two symmetric matrices

Let assume that I have an $n\times n$ symmetric matrix $A$ and I know $A^{-1}$. Now, I have a new matrix $$M = \begin{pmatrix} A & b \\ b^T & c \end{pmatrix},$$ where $b$ is a vector and ...
1
vote
1answer
31 views

How to prove or disprove the matrices formula

Could some one give me some hints about the following prove of disprove: (a) If $PXX^TP^T=QXX^TQ^T$, then $PX=QX$; (b) If $PXX^T=QXX^T$, then $PX=QX$. In the above formulas, $P$, $Q$ and $X$ are ...
2
votes
1answer
57 views

Eigenvectors of transition matrices in PageRank algorithm

In my probability course, we were discussing applications of Markov Chains to computer science -- in particular, how the PageRank algorithm goes about finding stationary distributions, and thus, ranks ...
0
votes
2answers
225 views

How to solve $Ax=b$ via backward and forward substitution on Matlab

How can I solve $Ax=b$ in Matlab code via LU factorization. I know that the command [L,U]=LU(A) stores the ...
2
votes
0answers
39 views

Wiedemann for solving sparse linear equation

I am new member. I am researching in Wiedemann algorithm to find solution $x$ of $$Ax=b$$ Firstly, I will show a Wiedemann's deterministic algorithm (Algorithm 2 in paper Compute $A^ib$ for ...
0
votes
1answer
45 views

help to find SOR optimal parameter $w$

Please let following linear system as $Ax=b$: $$\begin{array}{l} 6a{x_1} + {x_2} + {x_3} = 1\\ {x_1} - 3a{x_2} + 4{x_3} = 2\\ {x_1} + {x_2} - 2a{x_3} = 3 \end{array}$$ Help me to prove that the ...
0
votes
0answers
55 views

Induced matrix p-norm

Let $\|\cdot\|_p$ denote the $p$ norm $(p≥1)$ defined for every vector $x=(x_1,x_2,\ldots,x_n)^t\in\mathbb C^n$ by $\|x\|_p=(\sum|x_j|^p)^{1/p}$ and let $|||\cdot|||_p$ denote the matrix norm defined ...
1
vote
0answers
40 views

What's the point of 1-norm matrix estimation? Why not brute force?

Calculating (brute-force) 1-norm of a square matrix should take $O(n^2)$ operations, with a small factor involved. Apparently, there is an algorithm (link) for estimating 1-norm that takes $O(n^2 t)$ ...
3
votes
2answers
59 views

Calculating the determinant of $A$ with $A_{ij}=a$ for $i<j$, $A_{ij}=-a$ for $i>j$, $A_{ii}=x$, using a pen and paper

Let $$A = \left[\begin{array}{cccccc} x&a&a&a&\dotsm&a\\ -a&x&a&a&\dotsm&a\\ -a&-a&x&a&\dotsm&a\\ -a&-a&-a&x&\dotsm&a\\ ...
0
votes
1answer
31 views

Finding the minimum of Condition number for this matrix

Suppose $A=\left[ {\begin{array}{*{20}{c}} {0.1\alpha }&{0.1\alpha }\\ 1&{1.5} \end{array}} \right]$. How can we find minimum of condition number $k(A)=\Vert A\Vert \Vert A^{-1} \Vert$ (Assume ...
1
vote
0answers
33 views

Is it better to compute $A^tA$ once and then $Ax$ several times or compute $y=Ax$ and then $A^ty$ every time?

So I have this algorithm which given a matrix $A$ it assigns $A=A^tA$ outside the loop and then on the algorithm loop it solves multiple instances of $Ax$ for different $x$s, (meaning that it's ...
3
votes
2answers
93 views

Good Textbook in Numerical PDEs?

I am currently taking a course on Numerical PDE. The course covers the following topics listed below. Chapter 1: Solutions to Partial Dierential Equations: Chapter 2: Introduction to Finite ...
2
votes
1answer
47 views

Restoring matrix from covariance matrix

Given $ A^TA $, how to restore $A$? (Any $A$ which produces this $ A^TA $). Given matrix $ A^TA $, vector $b$, and vector $Ab$, how to restore a matrix $A$ ? Correction to 2: The vector $A^Tb$, ...
0
votes
1answer
56 views

Why won't my conjugate gradient algorithm work?

I made this simple Conjugate Algorithm on Matlab n = length(b); r0 = b - A*x0; p0=r0; k=1; n0=(r0')*r0; while n0 >= eps && k <= n ...
0
votes
0answers
111 views

update cholesky factorization

I need to compute cholesky(H'*H) where H is a big sparse rectangular matrix. After that H is modified by adding several lines. That is Hn = [H ; line_1 ; ... ; line_n] in Matlab. How can I recompute ...
1
vote
0answers
44 views

matrix with positive diagonal elements

I was wondering if a symmetric matrix with positive elements only in the diagonal (negative elsewhere) is any special beside the symmetry. Thanks in advance
2
votes
0answers
44 views

Find the solution of linear equation using Wiedemann/ Krylov method

I am using Wiedemann (some literature called Krylov method) to find the solution of a linear equation that defined as $$Mx=b$$ Instead of resolving entire elements of x (size $K \times 1$), we can ...
1
vote
1answer
20 views

If normal linear regression finds $A$ such that $AX \sim Y$, then how do I solve $BAX \sim Y$?

If normal linear regression finds $A$ such that $$AX \sim Y$$ then how should I solve $$BAX \sim Y$$ where $B$, $X$ and $Y$ are given (non-invertible) matrices? I could of course derive the solution ...
0
votes
0answers
21 views

order of convergence for approximations

Let $u \in L^{2}(0,1)$ and $0 < x_{1}< x_{2}<... < x_{n} = 1$, where x$_{k}$ = k$\cdot$h, n$\cdot$h = 1, a partition of the interval [0,1]. Define I$_{k}$(x) = 1 if x $\in$ [x$_{k}$, ...
0
votes
0answers
23 views

Location and perturbation of eigenvalues

This is a problem from Horn and Johnson's Matrix Analysis. I'm having trouble showing the bolded parts in the following paragraphs. In fact, I don't really understand what the sentences mean. I would ...
0
votes
1answer
43 views

Eigenvalue inequalities for Hermitian matrices

This is a problem from Horn and Johnson's Matrix Analysis. I've tried to follow the problem but I can't find a way to lead to the conclusion the problem is suggesting. Any solutions, hints, or ...
0
votes
0answers
29 views

A problem on Gersgorin cirle passing through the eigenvalue of an absolute matrix

I'm having trouble solving the following problem. I think I need to show that the matrix $D^{-1}|A|D$ has property SC, but I can't come up with a way to show it. I would really appreciate any ...
0
votes
1answer
18 views

A problem about a theorem on irreducible matrix

I'm stuck on a problem where I need to find a counterexample. I'm not sure how to come up with a reducible matrix to show that it doesn't satisfy the result of the following corollary. Any solutions, ...
0
votes
1answer
22 views

Suppose that $A \in M_n$ is strictly diagonally dominant. Show that $|a_{kk}|$ $\lt C_k'$, for at least one value of $k$

Suppose that $A \in M_n$ is strictly diagonally dominant. Show that $|a_{kk}|$$\gt C_k'$, for at least one value of $k=1,\dots, n$, where $C_k'$ denotes $A$'s deleted absolute column sums ($a_{kk}$ is ...
2
votes
1answer
38 views

Suppose that the $n$ Gersgorin discs of $A \in M_n$ are mutually disjoint. If $A$ is real, show that every eigenvalue of $A$ is real.

Suppose that the $n$ Gersgorin discs of $A \in M_n$ are mutually disjoint. (a) If $A$ is real, show that every eigenvalue of $A$ is real. (b) If $A \in M_n$ has real main diagonal entries and its ...
2
votes
1answer
31 views

Show that the intersection taken over the Gersgorin discs of all similar matrices of $A$ $=$ $\sigma (A)$

Show that $\bigcap_S G(S^{-1}AS)$ $=$ $\sigma (A)$; the intersection is taken over all nonsingular $S$, and $\sigma (A)$ is the spectrum of $A$. I'm lost as how to even begin to prove this fact. Any ...
1
vote
2answers
34 views

Domain for which this matrix is positive definite

What is the domain for which this matrix is positive definite? $$\left(\begin{array}{cc} 12x^2 & 1 \\ 1 & 2 \\ \end{array}\right)$$ I'm trying to figure this out. I know the ...
1
vote
0answers
62 views

Rayleigh quotient ($|r(q)-\lambda|=O(||q-x||_2^2)$ ?)

how to show $|r(q)-\lambda|=O(||q-x||_2^2)$ $r(q)=q^*Aq/(q^*q)$ and $\lambda$ is an eigenvalue, A is a Hermitian matrix. x is the unit eigenvector corresponding to $\lambda$. and q is a unit vector. ...
0
votes
1answer
76 views

Interpolation of polynomials

let $f(x)=2^x$ and $x_0=1$, $x_1=2$, $x_2=3$. Use divided differences to compute the interpolation polynomial $P(x)$ satisfying $P(x_i)=f(x_i)$, i=0,1,2 and $P'(x_1)=f'(x_1)$ and estimate error ...
0
votes
0answers
39 views

Is the following matrix Upper Hessenberg?

Does $$ A = \begin{pmatrix} 1 & 1 \\ -1 & -1 \end{pmatrix}$$ properly satisfy the definition of upper Hessenberg?
0
votes
0answers
361 views

Applying Central Difference (Finite Difference Method) in MATLAB

I was given a rather complicated few problems to solve in MATLAB using the central difference method, and I'd like some help figuring out how to translate this into code. The goal is to discretize ...
0
votes
0answers
37 views

Show that Newton’s Method is well-defined for all k and converges to 0 for $x_0>0$

Let $f : R → R$ with $f$ twice continuously differentiable, $\gamma > f''(x)>\delta, f(0)=0,f'(x)>\rho $ for $x ≥ 0$. Show that for any $x_0 > 0$ that Newton’s Method is well-defined for ...
0
votes
1answer
28 views

Generalized Eigensystems

I am looking for solution algorithms for a second order generalization of the eigenvalue problem. A, B, and C are n-by-n matrices, I is the n-dimensional identity matrix, $\lambda_i$ is an unknown ...
0
votes
0answers
23 views

Jacobi Iteration with Shift

The question is to solve a linear system using Jacobi iterations with a shift of mu = 5. My code converges very quickly, but it does not yield the results that MATLAB gives with the backslash ...
0
votes
0answers
21 views

Convergence of recursive application of finite-difference operator to $C^{\infty}$ functions

Let $f\colon \mathbb{R}\to \mathbb{R}$ be an arbitrary smooth function (whose extension to a complex differentiable function is entire, if it matters). Let $\mathbf{D}_{h}$ be a finite difference ...
1
vote
0answers
102 views

Meaning of singular Jacobian and workarounds to Newton's method

I'm currently working with Galerkin's method to solve differential equations and I have to retrieve unknown coefficients for the truncate expansion. This is just to set the background for why I need ...
1
vote
1answer
48 views

Derivative of $\|Ax-b\|_1$

Using least squares approximation $E^2 = \| Ax - b\|^2 = (a_1x - b_1)^2+...+(a_mx-b_m)^2$ The derivative of E^2 at the point $\hat{x}$ is zero if: $(a_1\hat{x}-b_1)a_1+...+(a_m\hat{x}-b_m)a_m=0$ ...
0
votes
1answer
40 views

vector space of natural numbers

I wonder, is it possible for the natural numbers (with zero) t be a vector space on SOME field? I understand why it cannot be over real numbers because of muliplication with negative scalar. BUT what ...
1
vote
0answers
22 views

LU Decomposition for the solution of two linear systems

Let's say I have the following linear system: \begin{equation} \left[ \begin{array}{cccc} S&&L^{T}&&A^{T}&&0\\ L&&0&&0&&0\\ ...
0
votes
0answers
21 views

Applying perturbed matrix to unperturbed eigenvector

Suppose we've got a matrix $P$ and a perturbed version $\hat{P}=P+E.$ Given that $v$ is an eigenvector of $P$ with $Pv=0,$ I'd like to get as sharp a bound as possible on $\hat{P}v$ (in terms of ...
0
votes
1answer
34 views

convolution on 2 by 2 matrices

Let $m$ be a positive integer, and let $A_1,B_1 \in \operatorname{SL}(2,\mathbb{Z})$. Can one always find matrices $A_2,B_2 \in \operatorname{SL}(2,\mathbb{Z})$ such that $$ A_1 \left( ...
0
votes
0answers
212 views

Matlab project - Jacobi method for tridiagonal matrices…

I have to do a project in Matlab to my University and I don't quite understand what I should do. I was given script that solves systems of equations with Jacobi's method with given tolerance and ...
1
vote
2answers
49 views

A function to convert a vector to a number and vise versa?

Sorry in advance if I didn't choose the right tags for the question, I wasn't sure. So I'm a programmer and writing a saving/loading system for data. The way I was serializing (saving) vectors is via ...
0
votes
1answer
30 views

Enciphered Message with linear enciphering function.

My semester tests are coming up and as I was looking through past papers I came across this question. I was missing a lot during the beginning of the year and this was no doubt covered during my ...
4
votes
3answers
40 views

Divergence of fixed-point iteration for real starting values

Consider the linear system of equations $Ax = b$ with invertible $A\in \mathrm{GL}(n,\mathbb R)$ and $b\in\mathbb R^n$. For $A = M - N$ with invertible $M$ the solution $x_* = A^{-1}b$ is a fixed ...
2
votes
1answer
41 views

Weed out numerical artifacts from matrix inversion

I am working with the inverses to a set of large sparse matrices (in Matlab). A key indicator for my application is the number of non-zero entries in each row, and I recently discovered that I was ...
0
votes
0answers
71 views

Strictly diagonally dominant matrix -LU factorization

Let $A\in\mathbb{C^{n\times n}}$ be strictly diagonally dominant. I want to show that the LU factorizations with and without partial pivoting are the same for these matrices. For start, I created ...
0
votes
1answer
52 views

Why base vectors are 1 in length? [closed]

I can't really find any substantial reference in the math literature that justifies the fact that basis vectors are usually $\begin{bmatrix}1&0&0\end{bmatrix}$ or ...
2
votes
1answer
51 views

Is there a function in MATLAB that will estimate the initial condition from a set of data?

I was given a state-space model of a system and a list of outputs for t=0 to t=5, sampled every 0.1 seconds and asked to approximate the initial condition. Is there a function in MATLAB that will take ...